1 Chapter 1. Declaration and Definition, DataTypes, Operators and Statements The topic in this chapter include: 1.1 Declaration and Definition 1.2 Data types 1.2.1 Primitive data types 1.2.2 Derived types 1.2.3 User-defined data types 1.3 Operators 1.4 Statements

2 1.1 Declaration and DefinitionBefore a name (identifier) can be used in a C++ program, it must be declared so that the computer know what kind of entity (type) the name refers to. E.g. char * name = "Ching-Shoei Chiang"; struct rational { float num, denum;}; const double pi = ; enum days { Sun,Mon,Tue,Wed,Thr,Fri,Sat }; exterm int no_of_student; extern float sqrt(float); Most of these declarations are also definitions; that is, they also define an entity for the name to refer to. Other declarations only declare a name, and the entity they refer to must be defined else where. E.g extern int no_of_dtudent; struct student;

3 There must always be exactly one definition for each name in a C++ program, but there can be many declaration, and all declarations must agree on the type of the entity refer to. E.g. int i,j,k; int k; E.g. extern int no_of_student; extern short no_of_student; E.g. extern int no_of_student; extern int no_of_student;

4  User-defined data types:C++ provides: Data types: Primitive data types: E.g. Derived types:  User-defined data types: Operators( to manipulate those types ) Statements ( for program flow control ) E.g. for ( ; ; ) { }; if ( ) { };     

5 { } { } { } 1.2.1 C++ Primitive data typesa. char: individual character or small integer (reprented in a machine byte). b. int: integer (reprented in a machine word). c. E.g. If a machine byte composed of 8 bits: sign char ch; char ch; char short int long { } sign (or unsign) integer. The size is machine dependent. { } sign unsigned float double long double floating point with single, double and extended precision value { } d.

6 1.2.2 Derived Types (a) A pointer variable holds values that are the addresses of objects in memory. E.g. int *ip; unsigned char *ucp; float *fp; char *sp = "sp is a pointer to the first character of this string" (b) Array Types An array is a collection of objects of a single data type. The individual objects are not named; rather , each one is accessed by its position in the array. int i, j[20] ; j[7] = i ; i = j[8] ;

7 (c) Reference types( address of operators )A reference type, sometimes refers to an alias,serves as an alternative name for the object with which it has been initialized. An reference object, like a constant, must be initialized. E.g. int val = 0 ; int &aliasval = val ; aliasval +=2 ; A reference can be thought of a special kind of pointer. Unlike a pointer, however, a reference must be initialized and, once initialized, a reference cannot be made to alias another object. E.g. int i = 1; int *ip = i; int *ip = &i; int *ip2 = ip; int *ip3 = &ip; int **ip3 = &ip; 1024 ip(1028) i: integer ip: pointer of integer ip3: address of pointer of a integer 1028 i(1) ip3(1024)

8 1.2.3 User-Defined Data Type(a) A enumeration type declare a set of symbolic integral constants. E.g. enum{Sun,Mon,Tue,Wed,Thr,Fri,Sat} ; E.g. enum{false,true} ; An enumeration may optionally be provided with a tag name . Each named enumeration defines a unique type and can be used as a type specifier for declaring identifiers. E.g. enum Boolean{false,true} Boolean pass = false;

9 (b) Class Types A user-defined data in C++, refered to a class, is anaggregate of named data elements, possibly of different types, and a set of operations designed to manipulate that data. E.g. // File count.h Class counter { private: unsigned int value; unsigned int min=0,max=65535; public: counter() { }; void increment() void decrement() unsign int current_value() }

10 // File usecount.c #include #include "count.h" main() { counter c; c.increment(); cout << " c = " << c.current_value(); c.decrement(); cout << "c = " << c.current_value(); }

11 (c) Typedef Name The typedef mechanism provides a general facility for introducing mnemonnic synonyms for existing predefined, derived, and user-defined data types. E.g. typedef double score; typedef Boolean Over6o; These typedef names can serve as type specifiers within the program: const N3A = 60, N3B = 60; score CS3A[N3A], CS3B[N3B]; Over60 PASS3A[60], PASS3B[60];

12 1.3 Operators An expression is composed of one or more operations. The objects of the operations are referred to as operands. The operations' are represented by operators'. Unary operators: Binary operators: (1) The evaluation of an expression performs one or more operations, yieliding a result.( integer value if not noted) (2) The data type of the result is determined by the data types of the operands. (3) Type conversions take place if more than one data type is present. (4) The precedence(associativity) of the operators determine the order of operator evaluation.

13 Operators: Arithmetic Operators: Equality Operators: Relational Operators: Logical Operators: Assignment Operators: Increment and Decrement Operators: The sizeof Operator: The arithmetic if operator: The comma Operator: The bitwise Operators:

14 Arithmetic exceptions: the evaluation of an Arithmetic Operators Example: 14.0 / 4 14 / 4 14 % 4 14.0 % 4 Arithmetic exceptions: the evaluation of an arithmetic expression will result in an incorrect or undefined value. E.g. Operator Function Expression syntax multiplication expr * expr * / division expr / expr modulus (remainder) expr % expr % expr + expr + addition - substraction expr - expr

15 Equality, Relational and Logical Operators: The equality, relational and logical operators evaluate to either true( represented by 1) or false( represented by 0; nonzero value evaluate to true). Operator Function Expression syntax ! logical NOT ! expr < <= > >= less than less than or equal greater than greater than or equal expr < expr expr<=expr expr> expr expr>=expr = = != equality expr = = expr inequality expr != expr && logical AND expr && expr || logical OR expr || expr 1 0 && 1 0 || 1 0 1 1 0 0 0 1 1 1 1 0 ! 0 1 E.g.

16 The left operand of the assignment operator Assignment Operators The left operand of the assignment operator ( = ) must be an lvalue. The effect of an assignment is to store a new value in the left operand`s associated storage. Compound assignment operator a op= b means a = a op b op E.g. if (( score = next_student_score())<60) score += 10 ; 

17 Increment and Decrement OperatorsThe increment ( ++ ) and decrement ( -- ) operators provide a convenient notional compaction for adding or subtracting 1 from a variable. The operand must be a lvalue. Each operator has a prefix and postfix form. The prefix form increments(decrements) before that value is used and the postfix form increments(decrements) after that value is used. E.g. // push value to a stack if ( !full()) array[++top] = value; // pop a value from the stack if ( !empty()) return array[top--];

18 Sizeof Operator The sizeof operator return the size, in bytes, of an expression or type specifier. It may occur in either of two forms: sizeof ( type-specifier ) sizeof expr; E.g. int ia[ ] = { 1,9,9,4 }; const sz = sizeof ia / sizeof ( int ); Application of the sizeof operator on a reference type returns the size of the memory necessary to contain the reference type itself.

19 1. The size of the type SHORT? 2. The size of the address of the type Exersise: How to decide 1. The size of the type SHORT? 2. The size of the address of the type SHORT? 3. The size of the reference of the type # include main() { } Notice that the answer for this program is machine dependent, and the sizeof(short) should have the same value a sizeof(short&).

20 The arithmetic if operator ( the only tenary operator in C++)expr1 ? expr2 : expr3; T expr1 expr2 expr3 E.g. cout << " The larger value of " << i << "and" << j << " is " << (i>j ? i : j) << "\n"; The comma operator A comma expression is a series of expression separated by a comma. These expression are evaluated from left to right. The result of a comma expression is the value of the rightmost expression. E.g. Boolean bval = ( is_empty()) ? cout << "Stack is empty \n" , true : cout << "Stack is not empty \n" , false ;

21 A bitwise operator interprets its operand(s) as The bitwise operators A bitwise operator interprets its operand(s) as an order collection of bits. A bitwise operator allows the programmer to test and set individual bits or bit subsets. The operands of the bitwise operators must be of an integer type. Operator Function Expression ~ bitwise NOT ~expr << left shift expr1 << expr2 >> right shift expr1 >> expr2 & bitwise AND expr1 & expr2 ^ bitwise XOR expr1 ^ expr2 | bitwise OR expr1 | expr2 ^

22 1, how do we know whether the 7th bits of unsigned char bv1 = 0321; //octal unsigned char bv2 = 1; //decimal unsigned char bv3 = 0x96; //hexidecimal unsigned char result ; bv1 = ~bv1; // bv1 = bv2 = bv2 << 3 ; // bv2 = bv2 >>= 1; // bv2 = result = bv1 & bv // result = result = bv1 | bv // result = result = bv1 ^ bv // result = Exersize: How to test individual bits? For example , if the right most bits numbered by 1, how do we know whether the 7th bits of the variable result is 0 or 1 ? Example:

23 Precedence Level Operator Function 17R :: global scope(unary)17L :: class scope(binary) 16L >, member selectors 16L [ ] array index 16L ( ) function call 16L ( ) type construction 15R sizeof size in bytes 15R , increment,decrement 15R ~ bitwise NOT 15R ! logical NOT 15R , unary minus,plus 15R *,& dereference, address-of 15R ( ) type conversion(cast) 15R new,delete free store management 14L >*, .* member pointer selectors 13L *, /, % multiplicative operators 12L , arithmetic operators 11L <<, >> bitwise shift 10L <, <=, >, >= relational operators 9L ==, != equality, inequality 8L & bitwise AND 7L ^ bitwise XOR 6L | bitwise OR 5L && logical AND 4L || logical OR 3L ?: arithmetic if 2R =, *=, /= assignment operator 2R %=,+=,-=,<<= 2R >>=,&=,|=,^= 1L , comma operator

24 Example: Identify the order of evaluation of The following compound expressions: (1) a = b + c * d << 2 & 8 a & 077 != 3 a = = b || a = = c && c < 5 c = x != 0 0 <= i < 7 f(1,2) + 3 a = b a = b = = c ++ a = b = c = 0 a[4] [2] *= *b ? c : * d * 2 (2) *p ++ *--p ++ a -- (int *) p-> m *p.m *a[i]

25 1.4 Statement: declaration-statement labeled-statementexpression-statement compound-statement selection-statement iteration-statement jump-statement We will illustrate if, switch, while, do, for, break, continue, return, and goto statements. The If statement : syntax: if (expression) statement; if (expression) statement1; else statement2 E.g. Let c = 0, consider the follow program: (1) if ( c = 0) cout << 1; else cout <<2; (2) if (c ==0) cout<<1; else cout <<2; (3) if ( c != 0) c ; cout << c; (4) if( c ==0) { ++c; cout << c; }

26 Dangling-else ProblemIf ( E1) If (E2) S1 ; ELSE S2 (1) If ( E1 ) If ( E2 ) S1 ; ELSE S2 ; If ( E1 ) { If ( E2 ) S1; else S2; } (2) If ( E1) If ( E2 ) S2; ELSE S2 ; If ( E2 ) S1; ELSE S2 ;

27 The switch statement ( alternative form for deeply nested if-else statement): // This program caculates the number of students with // specified range of score. main( ) { float score ; int below60, To70, To80, To90, ToTOP, Index; while ( cin >> score ) { Index = score / 10 ; switch ( index ) { case 6 : To70 ; break ; case 7 : To80 ; break ; case 8 : To90 ; break ; case 9 : case 10 : ++ToTOP ; break ; default : ++below60 ; break ; } ; }

28 syntax : while ( expression ) statement;The while statement: syntax : while ( expression ) statement; // This program caculates the // size of a string. int stringlen ( const char *st ) { int len = 0 ; const char *tp = st ; while ( *tp++ ) ++len ; return len ; } // This program copy a string. char * copystring ( const char *st ) { char *sst = st; int len = stringlen ( sst ); char *s = new char [ len + 1 ] // why + 1 ? char* sst = s; while ( *s++ = *st++ ) ; return sst ; } T expression statement F

29 The do statement: syntax : do statement ; while ( expression )do S1 ; S1; while ( E1 ) ; While ( E1 ) S1 ; (1) int i = 0 ; do ++i ; while (0 ) ; cout << i ; (2) while (0 ) ++i ; cout << i ; statement T expression F is equivalent to

30 The for statement: syntax :for ( init-statement ; expression1; expression2) statement; The for statement is equivalent to : init-statement; while ( expression1 ) { statement; expression2; } Example: The following program print out the multiplication table. main( ) { cout << "\n" ; for ( int i = 2 ; i < 10 ; ++i ) { for ( int j = 1 ; j < 10 ; ++j ) cout << i <<"x" << j << "=" << i*j << " "; cout << " \n " ; } } init-statement expression2 T statement expression1 F

31 The continue statement:The break statement A break statement terminates the smallest enclosing while, do, for or switch statement. The continue statement: A continue statement causes the current iteration of the nearest enclosing while, do, or for loop to terminate. for ( int i = 1; i < 9; ++i ) { if ( i == 5 ) break; cout << i ; } cout << "\ n" << i ; for ( int i = 1 ; i < 9; ++i ) { if ( i == 5 ) continue ; cout << " \n " << i

32 The return statement: Syntax return ; return expresasion ;E.g. // This program calculate the factorial of the positive // integer n. unsigned long factorial ( int n ) { if ( n > 1 ) return n * factorial ( n - 1 ) else return n; } E.g. // Compare whether two strings are equal enum Boolean { false , true } Boolean equal_string ( const char *s1, const char *s2 ) for ( ; *s1 && *s1 == *s2 ; ++s1, ++s2) ; if ( *s1 == *s2 ) return true ; else return false ;

33 syntax: goto identifier ;The goto statement: syntax: goto identifier ; identifier : statement ; A break or continue statement breaks out of only the innermost enclosing loop or switch. The goto statement break out from a nested loop or switch. E.g. Void f ( ) { for ( int i = 0; i < m ; ++i ) for ( int j = 0 ; j < n ; ++j ) if ( a[i][j] == val ) goto found ; // process for not found . found : // process for found.

34 Comments and Indentation:Judicious use of comment and consistent use of indentation can make the task of reading and understanding a program much more pleasant. Syntax for comments : // comment till the end of the line /* comment here */ E.g. // Ching-Shoei Chiang // Project # 1 or /************************** **************************/ Ching-Shoei Chiang Project # 1

35 Chapter 2 Function and scope This chapter includes:2.1. declaration and function definition 2.2. Argument 2.2.1 Argument list 2.2.2 default argument 2.2.3 unspecified number of argument 2.2.4 argument passing pass by value reference argument array argument pointers to function 2.3. overloaded function 2.4. template function 2.5. value returned 2.6. scope

36 2.1Function declaration : A function can be thought of as a user-defined operation. The operands of a function, referred to as its arguments, are specified in a comma separated as its argument list enclosed in parentheses. The result of a function is referred to its return type. Function declarations : A function declaration gives (1) the name of the function. (2) the number and types of the argument that must be supplied in a call of the function. (3) the type of the value returned ( if any ) by value.

37 Function Definitions :Every function that is called in a program must be defined somewhere ( once only ). A function definition is a function declaration in which the body of the function is presented. E.g. extern void swap ( int * , int * ) ; void swap ( int *p , int *q ) { int t = *p ; *p = *q ; *q = t ; }

38 Inline function : If a function has been declared inline, the body of the function is expanded at the point of its call during compilation. Otherwise, the function is invoke at run time. E.g. inline int min ( int i1 , int i2 ) { return ( v1 <= v2 ? v1 : v2 ) ; } int k = min ( i , j ); is expanded during compilation into int k = ( i <= j ) ? i : j ; It is significantly slower if we did not use inline for the function min, and call the function many times in the program ( two argument must be copied, machine registers must be saved, program must branch to a new location ).

39 Recursive Function : A function that call itself, either directly or indirectly, is referred to as a recursive function. E.g. // caculate the Fibonacci number // f(0) = 1 , F(1) = 1, f(n) = f(n-1) + f(n-2) unsigned long fib (int n) { if ( n == 0 || n == 1) return 1; return ( fib(n-1) + fib(n-2) ); } Exersize : Write a recursive function to find the greatest commom divisor for two positive integers.

40 2.2.1 Argument List : The argument list is referred as the signature of a function. The signature consists of a comma-separated list of argument types. No two argument names appearing in a signature may be the same. E.g. int min (int v1, v2 ); int min ( int v1, int v2 ); int min (int, int ); int min ( int , int ) { . }

41 2.2.2 A special signature : Default Initializers: A function may specify a default value for one or more of its arguments using initialization syntax within the signature. E.g. int score (int number,char sex = 'M',char* class = "CS3") int scorewho ; scorewho = score (83 ); scorewho = score (83,'F'); scorewho = score(83,'F',"CS4") ; scorewho = score ( ) ;

42 2.2.3 special signature : Ellipses... syntax : function-name ( arg-list,... ) ; function-name ( ...) ; Ellipses suspend type checking. Their presence tells the compiler that zero or more arguments may follow and that the types of the arguments are unknown. E.g. int min ( int i1, int i2, ...) void f ( ) ; void f (...); The call f( ) is legal invocation of both functions. How to process the the argument list specified by ellipses ? Please reference P of Stroustrup's book ---- The C++ Programming Language.

43 C++ is strongly typed language. Both the argument listArgument Passing : C++ is strongly typed language. Both the argument list and the return type of every function call are typed checked during compilation. If there is a type mismatch between an actual type and type declared in the function prototype, an implicit conversion will be applied if possible. If an implicit conversion is not possible or if the number of arguments is incorrect , a compiler error is issued Formal Argument and Actual Argument The argument list of a function describe its formal argument. The expression found between the parentheses of a function call are referred to as the actual argument. int min ( int i, int j ) { }; int minval = min ( 2*3, 7 ) ;

44 Pass - by - value: Pass-by-value is a reasonable default mechanism for argument passing in C++. (1) Evaluate the expression in actual argument. (2) Copy the value to the formal arguments which are local variable in the called function. (3) Even the formal arguments change its value during the execution of the called function, the value will NOT copy back to actual argument. E.g. Void swap ( int i1, int i2 ) { int temp = i1 ; i1 = i2 ; i2 = temp } main ( ) { int i = 1; int j = 2 ; swap ( i, j ); cout << i << j

45 What is the output for the following main program ? void swap ( int *i1 , int *i2 ) { int temp = *i1 ; *i1 = *i2 ; *i2 = temp ; } main ( ) int i = 1 ; int j = 2 ; swap(&i,&j); // i1 as the address of i cout << i << j ; 1024 i(2) i 1 (1024) 1028 j(1) i 2 (1028) temp(1)

46 Reference Argument : The declaration of an argument as reference overrides the default pass-by-value argument passing mechanism. The function receives the lvalue of the actual argument rather than a copy of the argument itself. void swap ( int &i1, int &i2) { int temp = i1 ; i1 = i2; i2 = temp ; } main ( ) { int i = 1; int j = 2; swap(i , j ) ; cout << i << j ;

47 Array in C++ are never passed by value(why?) Array Argument : Array in C++ are never passed by value(why?) Rather, an array is passed as a pointer to its zeroth element. E.g. // three equivalent declarations of functions // with array arguments void f ( int * ) ; void f ( int [] ) ; void f ( int [10] ) ; There is no checking of array size. main ( ) { int i, j[2], k[20] ; f (&i) ; f( j ) ; f( k ) ; f( i ) ; return 0 ; }

48 Pointer to Function The pointer obtained by taking the address of a function can then be used to call the function. E.g. void error ( char* p) { } void (*efct) (char*); void f ( ) { efct = & error ; (*efct)("anystring"); }. Pointers to functions have argument types declared just like the function themselves. void (*pf)(char * ) void f1 ( char * ) int f2 (char * ) void f3 ( int * ) void f ( ) { pf = &f1 ; pf = &f2 ; pf = &f3 ; (*pf)("Chiang"); (*pf) ( 1 ) ; int i = (*pf)("Chiang");}

49 E.g. We have been asked to provide a sorting functions which allows (1) different types of sorting object. (2) different sorting strategy. (1) different type of sorting object typedef int (*CFT)(void*,void*); void bubblesort(void* base,unsigned int n, unsigned int sz, CFT cmp ) /* Sort the "n" elements of vector "base" into increasing order using the comparison function pointed by "cmp ". The elements are of size 'sz'. Very inefficient algorithm : bubble sort */ { for ( int i = 0; i <= n-1; i++ ) for ( int j = n-1; i < j; j-- ) { char* pj = (char*) base + j*sz ; // b[j] char* pj1 = pj - sz ; // b[j-1] if (( *cmp )(pj,pj1 ) < 0 ) { // swap b[j] and b[j-1]: for ( int k = 0 ; k < sz ; k++ ) { char temp = pj[k]; pj[k] = pj1[k] ; pj1[k] = temp; }

50 struct user { char* name; char* id; int dept ; }; typedef user* Puser; user heads[] = { " Ritchie D.M", "dmr", , " Sethi R." , "ravi", , " Szymanski T.G.", "tgs", , " Schryer N.L. ", "nls", , " Schryer N.L.", "nls", , " Kernighan B.W.", "bwk", }; void print_id(Puser v, int n ) { for (int i = 0 ; i < n; i++ ) cout << v[i].name << `\t` << v[i].id << `\t` << v[i].dept << `\n`; } int cmp1 (const void* p, const void* q) { // campare name strings return strcmp (Puser(p)-> name, Puser(q)-> name ); int cmp2 (const void* p, const void* q) { // compare dept numbers return Puser(p)->dept - Puser(q) -> dept; int main( ) { bubblesort ( heads, 6, sizeof(user), cmp1 ); print_id (heads,6); // in alphabetical order cout << `` \n ``; bubblesort ( heads, 6, sizeof(user), cmp2 ); print_id (heads,6); // in department number order

51 (2) different sorting strategyextern void quicksort (void*, unsigned, unsigned,CFT ); extern void bubblesort(void*,unsigned,unsigned,CFT); typedef void (*PFA) (void*,unsigned,unsigned,CFT); extern Sort ( int*, int,int,PFA= bubblesort , CFT); For Sort: The first argument decides what kind of objects we are sorting, and the last argument decide the strategy we use. carray = {'a','e','i','o','u' } iarray = { 7, 5, 3, 3, 9, 6, 7 } int sc = sizeof(char) int si = sizeof(int) Sort( iarray,7,si,bubblesort,cmp3) Sort( carray,5,sc,quicksort,cmp4)

52 Using the name for different operations on different types2.3 Overloaded Function: Using the name for different operations on different types is called overloading. E.g. extern void print(char); // Label 1 extern void print(int); // Label 2 extern void print(unsign int); // Label 3 extern void print(char*); // Label 4 There are three possible outcomes of a call of an overloaded function: A match. No match. Ambiguous match. E.g. int *ip; unsigned int a; unsigned long ul; print('a'); print("a"); print(a); print(*ip); print(ip); print(5);

53 Match can be achieved in one of four ways, in the following order of precedence: 1. An exact match. 2. A match through promotion. 3. A match through application of a standard conversion. 4. A match through application of a user-defined conversion. E.g. extern void ff(int); extern void ff(char*); f(0); ff('a'); . E.g. class X; extern void ff(X&); ff(0); User-defined conversion will introduced in the future.

54 2.4 Template Function: A template defines a family of types or functions. Syntax: template-declaration: template < formal-argument-list > declaration formal-argument-list: formal-argument. formal-argument-list, formal-argument. formal-argument: type-argument argument-declaration type-argument: class identifier E.g. template Type min(Type a, Type b){ return a < b ? a:b; } main(){ min(10,20); min(100,200); return 0; }

55 E.g. template Type min(Type, Type); template If there are no "template", strong-types requires that we imploment an instance for each type pair we wish to compare. int min(int a,int a){return a double min(double a,double b){return a long min(long a,longb){return a unsigned int min(unsigned int a, unsigned int b) { return a

56 What's wrong if use the following macro forthe function main()? #define min(a,b)((a)<(b) ? (a):(b)) int ia[]={1,4,5}; int ib[]={2,3,6}; main(){ int i = 0, j = 0; cout< cout<< i << j }

57 Declaration of template function:1. Each formal parameter must appear at least one in the signature of the function. 2. The names of the formal parameters do not need to be the same across forward declarations and the definition of the template. 3. A template function can be declared extern, inline, or static the same as a nontemplate function. The specifier is placed following the parameter list. 4. The name of the formal parameter remains in scope for the extent of the template definition. (The "scope" will describeed later) E.g. (1) template T1 f1(T2,T3); (2) template T min(T,T); template Type min(U a, U b){...} (3) template inline T min(T,T); extern template T min(T,T);

58 Function Template InstantiationThe function template specifies how individual functions can be constructed given a set of one or more actual types. This process of construction is referred to as instantiation. The determination of the actual type to which to bind its type is made by an evaluation of the actual first argument, the return type is not considered. E.g. template T min(T a, T b){return a #include main(){ int i = 1, j = 2; double d = 3.5, e = 0.5; //instantiated to int min(int a,int b){return a int k = min(i,j); f=min(i,j); k=min(i,e); //instantiated to double min(double a, double b){return a double f = min (d,e); f=min(d,j); k=min(d,i); f = min(d,i); return 0 ; }

59 Overloading Template Function A template function can be overloaded provided that the signature of each instance can be distinguished either by argument type or number. E.g. template T min(T a, T b) { return a < b ? a:b; } template < class T > T min(T a, T b, T c) { T d = a < b ? a:b; return c < d ? c:d; } T min(T* array, int size) { T min_val = array[0]; for ( int i = 1; i if ( array[i] < min_val) min_val = array[i]; return min_val ;

60 Template Function Exampletemplate void qsort(Type *ia, int low, int high) { // qsort if (low < high) { int lo = low; int hi = high + 1; Type elem = ia[low] ; for ( ; ; ) { while (ia[++lo] < elem) ; while (ia[--hi] > elem); if (lo < hi) swap(ia, lo, hi); else break; } swap(ia, low, hi); qsort(ia, low, hi-1); qsort(ia, hi+1, high);

61 template < class Type >static void swap (Type *ia, int i, int j) { // swap two elements of an array Type tmp = ia[i]; ia[i] = ia[j]; ia[j] = tmp; } #include template void display(Type *ia, int size) { // display format : < > cout << "< "; for (int ix = 0; ix < size; ++ix) cout << "> "; #include "pt_sort.c" #include "pt_display.c" double da[ ] = { 26. 7, 5.7, 37.7, 1.7, 61.7, 11.7, 59.7, 15.7, 48.7, 19.7, }; int ia[ ] = { 503, 87, 512, 61, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677, 765, };

62 main () { int size = sizeof(da)/sizeof(double); cout << "Quicksort of double array (size == " << size << ")" << end1; qsort(da, 0, size-1); display(da, size); size = sizeof(ia)/sizeof(int); cout << "\nQuicksort of int array (size == " << size << ")" << end1; qsort(ia, 0, size-1); display(ia, size); return 0; }

63 2.5 Value returned The return type of a function may be1. a predefined type 2. a derived type 3. a user-defined type E.g. enum Boolean {false, true}; class student {/* define here */ } int min(int, int); char* stringcopy(char*, const char*); Boolean isequal(int, int); Student new_student(char*, int); void quicksort(int * , int, int); int[10] quicksort(int *, int, int); int * quicksort(int *, int, int); Reference the return statement, in chapter 1.

64 2.6 C++ supports three kinds of scope: 1. File scope-- A name declared outside all blocks and classes has file scope and can be used in the translation unit in which it is declared after the point of declaration. Name declared with file scope are said to be global. 2. Class scope-- The name of a class member is local to its class and can be used only in a member function of that class. 3. Local scope-- A new declared in a block is local to that block and can be used only in it and in blocks enclosed by it after the point of declaration. Names of formal arguments for a function are treated as if they were declared in the outermost block of that function.

65 Activation Record A activation record is an object holding all of theinformation relevant to one activation of an executable unit ( procedure , function , or program ). When a function is called , a new activation record is created , it stores the components needed for an activation of the function at run time. Upon termination of the function, its activative record is popped from the run-time stack. The activative contains: 1. Storage for parameter. 2. Storage function result. 3. Storage local variable. 4. Some " housekeeping " data such as return point.

66 Dangling Reference When the address of a local variable is passed outside its scope, it is referred to as a dangling reference. int* p; { int i ; p = &i; } .

67 Local variable int i = 0; // gloabal i; void f () { cout << i << "\n" ; // print 0; int i = 1; int { cout << i << "\n"; int i = 2 ; } int i = 2;

68 A for loop permits definition of variableswithin its control structure. Variables defined inside the for loop control are entered into the same scope as the for statement itself, so, the following two program segments are the same: 1. for ( int i = 0; i < n; ++i ) { } 2. int i; for (i = 0; i < n; ++i) { } E.g. for ( int i = 1 ; i < 10 ; ++i ){ cout << i << " "; for (int j = 1; j < 10 ; ++j ) cout< } cout << i << "\n"; cout << j << "\n";

69 The value of a static local variable persists accross invocations, its access remains to its local scope. #include int Gcd ( int v1, int v2 ) { static int depth = 1; cout << depth++ << ":(" << v1 << "," << v2 << ")" << "\n" ; if (v2 == 0) { depth = 1; return v1; } return Gcd(v2,v1/v2); #include < iostream.h > extern int Gcd (int, int) main() { int result = gcd (49,77); cout<<"gcd of (49,77):"< return 0 } What is the output for the program ?

70 3.1 Abstraction data type(ADT), encapsulation, andChapter 3 Class 3.1 Abstraction data type(ADT), encapsulation, and data hiding 3.2 Class definition 3.3 Members of a class 3.4 Private, protected, and public sections 3.5 Member functions Constructors and Destructors Memberwise Initialization Operator and Function Overloading 93 User-defined Conversion 3.6 Friend function of a class 3.7 Class scope 3.8 Class Templates 3.9 Examples: A Template Array Class

71 3.1 Abstraction data type (ADT), encapsulationand data hiding. Procedure-oriented language, structured programming, and the data-structure-problem solving paradigm have led to modest improvements in software efficiency and relibality, particularly for small- to moderate-size software system. The major defect of the data-structure-problem solving paradigm is the scope and visibility that the key data structures have with respect to the surrounding software system. The implementation of many important procedures and functions in such systems is critically dependent on the key data structures. If any changes are made to one or more of these key data structures, the fall-out effects on the software system may be pervasive.

72 Encapsulation and data hiding bind data and procedures tightly together and limit the scope and visibility of the procedures and functions that can manipulate the data to a highly localized region of code in the software system. Indeed, the data and related procedures and functions become inseparable. A new entity, an object, is defined. An object has its own data and its own procedure. The object has sole access to and assumes full responsibility for manipulating its private data using its private procedures and functions. The user can manipulate the object through a precisely specified set of methods, which are activated by passing messages to an object. Objects assume control of the system and pass messages to other objects. The architecture of an object-oriented software system is not dependent on an object's internal structure but only on the methods that define the operations that can be performed on the object's internal data.

73 An abstract data type is a software model that specifies an allowable set of values for data and a set of allowable operations that can be performed on the data. The binding of underlying data with an associated set of procedures and functions that can be used to manipulate the data is called encapsulation; the inaccessibility of the internal structure of the underlying data is called data hiding. Conventional procedural approach Object-oriented approach is replaced by data structure hierarchy class hierarchy procedure hierarchy

74 The class mechanism allows users to define their own data types. C++ class The class mechanism allows users to define their own data types. A C++ class has four associated attributes 1.A collection of data member. 2.A collection of member function. 3.Level of program access. Menbers of a class may be specified as private, protected, or public. 4.An associated class tag name, serving as a type specifier for the user defined class. E.g. class point { privated: int xx, yy; public: point(int, int); int x-coord(); int y-coord(); }

75 3.2 Class definition 1. A class definition has two parts: class head and class body. E.g. class point { float x,y ; public: point (int xx, int yy) {x=xx;y=yy;}; int x_coord(); { return x; }; int y_coord(); { return y; }; }; 2. The declaration of class data menber is the the same as for variable declarations with the exception that an explicit initializer is not allowed. 3. The set of sperations to manipulate point object is declared within the class body. Those operations are spoken of as the member functions of the class. 4. The member function of a class are declared inside the class body. A declarations consists of function prototype. E.g. point(int , int); int x_coord(); The definition of a member function can be placed inside the class body.

76 3.3 Member of a class Data Member◎ The declaration of class member is the same for variable declarations with the exception that an explicit initializer is not allowed. ◎ A class object can be declared as a data member only if its class definition has already seen. In cases where a class definition has not been seen, a forward declaration of the class can be supplied. ◎ A class may define pointer and reference data members of its own class type. E.g. class Node { char * last_name, *first_name ; char age; } class Tree { Node info ; Tree *left, *right ; } As a rule, good programmer always declare the member data of a class in order of increasing size. This usually gives optimal alignment on all machine.

77 Member function The set of operations to manipulate the data member ofa class is declared within the class body. This set is referred to as the public interface of the class. These operations are spoken of as the member function of the class. E.g. class point { float x, y ; void write ( ); } If the definition of a member function is short, it can be placed inside the class body. Otherwise, it can defined outside the class body. #include"point.h" #include #include void point::write( ) { cout << "x= " << x << "\t" << "y= " << y << "\n" ;

78 Class objects ◎ Class object is defined by: class_Tag object_name;E.g. point p; // p is a point; ◎ Objects of the same class can be initialized and assigned to one another. E.g. point q = p; // assign value of p to q; ◎ A pointer to a class object can be initialized or assigned the result either of operator new or of the address_of ("&") operator. E.g. point *pp = new point; pp = &p ; ◎ The class object selector (".") and class selector ("->") are used to access either the member data or member functions outside the scope of the class. E.g. main ( ) { point p, *q ; p.write ( ) ; cout<x_coord( ); }

79 3.4 Private, Protected, Public sectionsA C++ class contain up to three sections: ◎ Private: The data and functions ( class members ) declared in private section of a class are not accessible outside the class. (data hiding ) ◎ Protected: The data and functions declared in protected section of a class are not accessible outside the class except within subclasses derived from the given parent class. ◎ Public: The data and functions declared in the public section of a class are available outside the class. Normally the operations that can be performed on an abstract data type are specified in the public section of the class.

80 point (float, float); //constructor E.g. class point { private: float x, y; public: point (float, float); //constructor void write( ) {cout< float x_coord{return x}; float y_coord{return y}; } # include #include main( ) { point p(1.0, 2.0); cout< cout< return 0;

81 Constructor A class object is initialized by the initialization of data member. E.g. class point { public: float x, y;} // explicit member initialization point p = {10, 10}; C++ suports a special class member fuction, called a constructor, to initialize the class objects automatically. private: float x, y ; point(float xx, float yy) { x = xx; y = yy }; write () { cout<< x<<"\t"< } main() { point p(1.0, 2.0); const point q ; const point r (3.0,4.0); p.write(); }

82 A constructor is identified by assigning it the tag name of a class. It may be overloaded to provided a set of alternative initializations. E.g. class string { private : int len; //length of the string; char *str; // address of the string; public : string(const char*); string(int); }

83 string::string (int ln) { len = ln ; #include #include string::string(const char *s) // why const ? { len=strlen(s); //strlen(s) return the length of the string; str=new char[len+1]; assert (str ! = 0 ); //str is never set to 0 after the //call of new. Otherwise, the //program terminates with an // error message strcpy(str,s); // copy a string } // Can we use str=s instead ? string::string (int ln) { len = ln ; str = new char[len + 1]; //Is this the same as //str = new char[++len]; assert (str != 0 ); str[0] = '\0' ; //initialize as a null string; }

84 int len = 1024; string s ; string s[&len] ; string s("Soochow",7); string s = string("Soochow"); string s("Soochow"); string *ptrstr = new string(10); string st() ; Homework: Define a single string constructor that accepts all the following declarations: string s1("rosebud", 7) ; string s1("rosebud", 8) ; string s2("", 1024) ; string s3("The Raw and the Cooked"); string s4 ;

85 Destructor ◎ A special, user-defined member function referred to asa destructor, is invoked whenever an object of its class goes out of scope or operator delete is applied to a class pointer. ◎ A member function is designed the class destructor by giving it the tag name of the class prefixed with a tilde ("~"). E.g. string::~string() { delete str ; } ◎ A destructor "deinitializes" the class object prior to the normal deallocation of storage that occurs when an object goes out of scope. E.g. #include "string.h" string q(10); void f() { string best("Soochow"); //constructor string *p=&best; q = p ; string *pp = new string("Univ"); : delete pp ; }

86 Questions: 1. What happend if we don't delete pp ? 2. When f() is called, the string constructor will called for "best" to allocate memory. At the return from f(), this memory will be free. After f returned, what happen to q ?

87 Menberwise InitializationConsider this example: string school("Soochow") string best = school The initialization of best is accomplished by copy the each member of "school" into the corresponding member of "best". This is referred to as memberwise initialization. The compiles accomplishes memberwise initialization by internally defining a special constructor of the following general form: x::x(const x&); E.g. string::string (const string& s) //memberwise initialization { len = s.len; str = s.str ; } Compare with the constructor we defined: string:::string (const char* s) { len = strlen(s); str = new char[len+1]; assert (str != 0); strcpy (str, s) ; }

88 // This code defines a class for a singly linked list.// File list.h. #include class node { friend class list; private: node* next; char* contents; //contents dynamically allocoated }; class list node* head; int size ; public: list(int s){head=0; size=s;} void insert(char* a); void append(char* a);. char* get(); . void clear(); ~list() {clear();}

89 // Implementation of class list// File list.cpp #include "list.h" void list::insert(char* a) { node* temp; temp = new node; temp->contents = new char[size]; for (int i = 0; i temp->contents[i] = a[i]; if ( head ) temp->next = head; head = temp; } else temp->next = 0;

90 void list::append(char* a){ node *previous, *current, *newnode; if ( head ) previous = head; current = head->next; while ( current != 0 ) previous = current; current = current->next; } newnode = new node; newnode->contents = new char[size]; newnode->next = 0; for ( int i = 0; i < size; i++ ) newnode->contents[i] = a[i]; previous->next = newnode; else { head = new node; head->contents = new char[size]; head->next = 0; for ( int i = 0 ; i head->contents[i] = a[i];

91 char* list::get() { if ( head == 0) printf("Error--> get() from empty list"); else char* r; r = new char[size]; node* f = head; for ( int i= 0; i r[i] = f->contents[i]; head = head->next ; return r ; } void list::clear() node* l = head; if (l == 0) return ; do node* ll = l; l = l->next ; delete ll->contents; delete ll ; } while ( l != 0 ) ;

92 // A test program that uses class list// File listst.cpp #include "list.h" main() { list my_list(sizeof(float)); float *r; *r = 1.5; my_list.insert((char* ) r ); *r = 2.5 ; *r = 3.5 ; *r = 6.0 ; my_list.append((char* ) r ); for (int i = 0 ; i < 4 ; i++ ) r = ( float*)my_list.get(); printf("\n%f",*r); } The output for the main program is

93 Operator Overloading A class designer can provide a set of operators to work with objects of the class. An operator function need not be a member function, but it must take at least one class argument. Operator += E.g. Concatenate two strings S1 + S2 S1+S2 means concatenate S1 with S2 and assign the value to S1. #include #include string & string::operator += (const string &s ) {len += s.len ; char* p = new char[len+1]; assert ( p != 0 ); strcpy (p ,s.str ); strcat (p, s.str ); delete str ; str = p ; return *this ; } #include #include "string.h" main() { string s1("Soochow "); string s2("University "); s1 += s2 ; cout << s1 << "\n"; return 0 ; str (free the memory) S o o c h o w s U n i v e r s i t y p S o o c h o w U n i v e r s i t y

94 Operator + E.g. Concatenate two string. S1+S2, treat it as s1.(s2)string::operator+(const string &s) const { string result = *this; result += s; return result; } main() { string s1("Soochow "); string s2 ("University "); string best = s1+s2; string question=best+"really?"; string name="The"+best; return 0;

95 - ! , = < > <= >= ++ -- << >> == != && || Only the predefined set of C++ operators can be overloaded. These operators follow the operators precedence rules. That is, regardless of the class type and operator inplementation, x==y+z will always perform operator + before operator == Overloadable Operators * / % ^ & | ! , = < > <= >= << >> == != && || += -= /= %= ^= &= |= *= <<= >>= [ ] ( ) -> ->* new delete

96 Operator [ ] Operator( ) inline char& string::operator(int elem) {assert(elem >= 0 && elem < len); retuen str[elem]; } main() { string st("Soochow"); st[0]='s'; cout << st ; Operator( ) class string { private: int len, index; char *str; public: char operator(); } char string::operator() { char ch=str[index]; index = (index == len) ?0 : index + 1; return ch; }

97 Operator ++ and -- Both a prefix and postfix instance of the increment and decrement operators can be defined. A postfix instance of instance of either operand is defined by specifying a second argument of type Int. #include class counter { private: unsigned int value; public: counter ( ) { value = 0 } void operator ++( ); void operator ++(int); void operator --( ); void operator --(int); unsigned int operator( )( ); }

98 #include "count.h" inline void counter::operator++() { if (value < 65535) ++value; } inline void counter::operator--() { if (value < 0 ) --value ; } inline void counter::operator++(int) { if (value < 65535) value++ ; } inline void counter::operator--(int) { if (value < 0 ) value--;} unsigned int counter::operator()() { return value; } main() { counter c; cout<<++c< cout << c; //output 2 return 0 ; }

99 Operator << and >>E.g. ostream& operator<<(ostream &s, string& st) { return(s << st.len << '\t' << st.str); } istream& operator>>(istream &s, string& st) { int length; s>>length; char buffer[length+1] s>>buffer; st.len = len; st.str = buffer; return s ; } main ( ) { string best(20) ; cin >> best ; cout << best << "\n"; return 0;

100 Operator= The assignment of one class object with another object of its class is performed as the memberwise assignment of the nonstatic data members. String& String::operator=(const String& s) { len = s.len; str = s.str; return *this; } What are the problems for the following program segment? String best("T University"); String better("Soochow University"); best = better; better[8]="u"; cout << best; Problems: 1. Garbage which contains "T University" exists. 2. A modification to the characters in the variable "better" will also change the characters in the variable "best".

101 The esigner of the class can resolve these problems by providing an explicit instance of the memberwise assignment operator. String& String::operator=(const String s) { if (this == &s) // Why this if statement? return *this; len = s.len; del str; str = new char[len+1]; strcpy(str, s.str); } Consider the following example: main() { String s1("The Soochow University"); String s2; s2 = s1; cout < s2=s2;

102 There are many operators which are used often to implement a systemThere are many operators which are used often to implement a system. For example, the operators new and delete are used to deallocate and allocate memory. (Text book page ). Each operator has an associated meaning from its predefined use. Binary +, for example, is strongly identified with addition. Mapping binary + to an analogous operation within a class type can provide a convenient notational shorthand. For example, String concatenation, which adds one String to another, is an appropriate extension of binary +. An ambiguous operator is one that supports equally well a number of different interpretations. When the meaning of a class operator is not obuious, it is probably a good idea not to provide it. Once the public interface of the class is defined, look for a logical mapping between the operation and an operator: isEmpty(): the logical NOT operator, operator!(). isEqual(): the equality operator, operator==(). copy(): the assignment opoerator, operator=().

103 class X {/* ..... */ X(int); };Conversions Type conversions of class objects can be specified by constructors and by conversion functions. A constructor accepting a single argument specifies a conversion from its argument type to the type of its class. class X { // ... public: X(int); X(const char*, int=0); } void f(X arg) { X a = 1; X b = "Soochow"; a = 2; f(3); } When no constructor for class X accepts the given type, no attempt is made to find other constructors or conversion functions to convert the assigned value into a type acceptable to a constructor for class X. class X {/* */ X(int); }; class Y {/* */ Y(X); }; Y a = 1;

104 class complex{ double re, im; public: complex(double r, double i){re = r; im = i; } friend complex operator+(complex, complex); friend complex operator+(complex, double); friend complex operator+(double, complex); friend complex operator-(complex, complex); friend complex operator-(complex, double); friend complex operator-(double, complex); complex operator-(); // unary - friend complex operator*(complex, complex); friend complex operator*(complex, double); friend complex operator*(double, complex); // }; void f(){ complex a(1,1), b(2,2), c(3,3), d(4,4), e(5,5); a = -b - c; b = c*2.0*c; c = (d+e)*a; } It is tedious to write each combination of complex and double.

105 An alternative way using several functions is to declare a constructor that, given a double, creates a complex. class complex { // ..... complex(double r) {re = r; im = 0; } complex z1 = complex(23); complex z2 = 23; A constructor is a prescription for creating a value of a given type. When a value of a type is expected, and when such a value can be created by a constructor, given the value to be assigned, the constructor will be used. double re, im; public: complex(double r, double i=0) {re = r; im = i; } friend complex operator+(complex, complex); friend complex operator*(complex, complex); complex operator+=(complex); complex operator*=(complex); /* */ }; Now, a=b*2 means

106 A member function of a class X with a name of the form conversion-function-name:operator conversion-type-name specifies a conversion from X to the type specified by the conversion-type-name. class X{ // ..... public: operator int(); }; void f(X a) { int i = int (a); i = (int) a; i = a; } void g(X a, X b) { int i = (a) ? 1+a: 0; int j = (a && b) ? a+b: i; if (a) {/* */ } }

107 Example: BitVector Class (page 326-334 text)typedef unsigned int BitVecType; typedef BitVecType *BitVec; class BitVector { Private: BitVec bv; unsigned short size; short wordWidth; inline getIndex(int) const; inline getOffset(int) const; public: BitVector(int,int); void operator+=(int); void operator-=(int); void operator ==(int) const; void operator !=(int) const; BitVector& reset(); BitVector BitVector::operator|(const BitVector&) const; ostream& operator << (ostream&, BitVector&); };

108 The bit and byte sizes of data types are guaranteed to vary among different machines, so we want to localize the explicit references to these machine-dependent values in our code: #ifdef vax const BITSPERBYTE = 8; const BYTEPERWORD=4; #endif #ifdef sun // The size of a machine integer const WORDSIZE = BITPERBYTE * BYTEPERWORD;

109 The constructor for BitVector class:#include enum {OFF, ON}; // default values: sz => WORDSIZE, init => OFF BitVector::BitVector(int sz, int init) { assert (sz > 0); size = sz; wordWidth = (size + WordSize - 1) / WORDSIZE; bv = new BitVecType [wordWidth]; assert(bv !=0); if (init !=OFF) init = ~0; for (int i=0; i *(bv+i) = init; }

110 Void BitVector::operator+=(int pos){ assert (pos >= 0 && pos < size); int index = getIndex (pos); int offset = getOffset (pos); *(bv+index) |= (ON << offset); } *(bv+index) &= (~(ON << offset)); } inline BitVector::getIndex (int pos) const { return (pos / WORDSIZE); } inline BitVector::getOffset (int pos) const { return (pos % WORDSIZE); }

111 BitVector::operator==(int pos) const{ assert(pos >= 0 && pos < size); int index = getIndex(pos); int offset = getOffset(pos); return* *(bv+index) & (ON << offset) ); } BitVector::operator !=(int pos) const { return ( !(*this == pos)); } ostream& operator<<(ostream& os, BitVector& bv) { os << "<"; for (int i=0; i if(bv==i) os< return os << ">"; } BitVector& BitVector::reset() for (int i=0; i *(bv+i) = 0; return *this; }

112 BitVector BitVector::operator|(const BitVector& b) const { // simplifying assumption: both have same size BitVector result(size, Off); BitVec tmp = result.bv; for (int i=0; i< wordWidth; ++i) *(tmp + i) = *(bv + i) | *(b.bv + i); return result; } *(tmp + i) = *(bv + i)&*(b.bv + i);

113 #include#include #include "BitVector.h" const int maxBits = 8 ; enum { ERROR, CHAR, SHORT, INT, PTR, REFFERENCE, CONST, UNSIGNED }; static char *typeTbl[] = { "OOPS, no type at slot 0", "char", "short", "int", "*", "&", "const", "unsigned" }; static char *msg = "Type in a declaration -- end with ';' \ \npreceded by white space. For example, \ try \n\t'unsigned const char * ;'\ \nHit ctrl-d to exit program\n";

114 main() { BitVector typeFlags ( maxBits ) ; char buf[1024]; cout << msg ; while ( cin >> buf ) { for (int i = 0; i if (strcmp(typeTbl[i], buf) == 0) {// a keyword? BitVector::operator+=() typeFlag += i ; break ; } if (buf[0] == ';' ) { // end of entry cout << "\nflags set for declaration are :\n\t"; for ( i = maxBits-1; i>0; i--) // BitVector::ooperator==() if(typeFlags == i) cout << typeTbl[i] << "\n\t"; cout << endl; // reinitialize: BitVector::reset() typeFlags.reset(); } } } When compiled and executed, the program generates the following output: Type in a declaration -- end with ';' preceded by white space. For example, try 'unsigned const char *;' Hit cntl-d to exit program unsigned const char *; flag set for declaration are: unsigned const * char

115 3.6 Friend function of a classWhat are friends for? The friend mechanism gives nonmembers of the class access to the nonpublic members of a class. Why "friend" is necessary? We would like to output the data in a class POINT as the following: POINT p; cout << "The point p is equal to " << p << "\n"; The output operators require an ostream object as their left operand; both return the object upon which they operate. This allows successive output operators to be concatenated. For example, (((cout << "The point p is equal to ") << p) << "\n") Each parenthetical subexpression returns the ostream object "cout", which becomes the left operand of the next outermost expression. The following functions are implemented already: // cout for character string. cout << "The point p is equal to "; // cout for special character "\n" (change line) cout << "\n"; We have to implement the output for the class object. cout << p;

116 So, the declaration of the output for class object is:ostream &opoerator<<(ostream&, Point&); This implementation, however, precludes defining the operator function as a member function of Point. If we want declare the output operation as a member function of the class Point, the declaration will be: class Point{ Public: // Why public? ostream &operator << (ostream&); // ... } The left operand of every member function is an object or pointer to an object of its class. A call of this instance takes the following form: p << cout; or "\n" << p << "The point p is equal to " << cout; It would be very confusing both to the programmer and the human readers of the program to provide this instance. Notice that the output operator cannot access the private data member of the class Point. Sometimes we would like to display the private data member for debug purpose, this is where the friend mechanism comes in.

117 A friend is a nonmember of a class that is given access to the nonpublic members of a class. A friend may be a nonmember function, a member function of a previously defined class, or an entire class. In making one class friend to another, the member functions of the friend class are given access to the nonpublic members of the class. A stylistic convention is to group all friend declarations immediately following the class header, the output Point operator might be: class Point{ // nonmember function friend ostream& operator<< (ostream&, Point&); private: // member function int x,y; public: // }; #include ostream& operator<<(ostream& os, Point& p) { os << "(" << x << "," << y << ")" << "\n"; } The input operator ">>" may be implemented similarily. (Reference the text book page )

118 If a function manipulates objects of two distinct classes, the function may either be made(1) a friend to both classes. (2) a member function of one class and a friend to the other. Consider the class we defined in the second project. Let Ipoint, Fpoint and Rpoint are the classes for grid points, real points and rational points. Example of (1): class Fpoint; class Ipoint { friend Boolean operator==(Fpoint&, Ipoint&); // ... }; class Fpoint{ friend Boolean operator==(Fpoint&,Ipoint&);

119 Example of (2): class Ipoint; class Fpoint{ friend ostream& operator<<(ostream&,Fpoint&); public: // member of one class, a friend to a second class Fpoint& operator=(Ipoint&); Fpoint& operator=(Fpoint&); /* ... */ }; class Ipoint{ friend Fpoint& Fpoint::operator=(Ipoint&); friend Fpoint& operator*(float); Fpoint::operator=(Ipoint&){ /* ... */ } #include "point.h" main() { Fpoint rp; Ipoint ip(1,2); rp = ip; cout << rp; rp = ip * (float) 1.5; cout <

120 A entire class can be declared as a friend to another class.For example: class Ipoint; class Rpoint{ friend class Ipoint; // ... }; The nonpublic members of the Rpoint may now be accessed within each of the Ipoint member function. A class must specify each instance of an overloaded function it wishes to make a friend to the class. For example, extern Fpoint& assign(Fpoint&,Ipoint&); extern Rpoint& assign(Rpoint&,Ipoint&); class Ipoint { friend Fpoint& assign(Fpoint&, Ipoint&); friend Rpoint& assign(Rpoint&,Ipoint&); }

121 Example : Rational Number :class Rational { friend ostream& operator<<(ostream&,Rational&); friend istream& operator>>(istream&, Rational&); private: long numerator, denominator; void simplify(rational &); public: Rational(long num=0, long den=1) //constructor { numerator = num ; denominator = den ; simplify(*this); } Rational& operator=(Rational &); Rational& operator=(long); Rational& operator = (float); Rational& operator +=(const Rational&); Rational& operator -=(const Rational&); Rational& operator *=(const Rational&); Rational& operator /=(const Rational&); Rational& operator +(const Rational&) const; Rational& operator -(const Rational&) const; Rational& operator *(const Rational&) const; Rational& operator /(const Rational&) const; int operator == (const Rational&) const; int operator != (const Rational&) const; }

122 3.7 Class Scope: There are four kinds of scope: local, function, file and class. Local: A name declared in a block is local to that block and can be used only in it and in blocks enclosed by it after the point of declaration. Names of formal arguments for a function are treated as if they were declared in the outermost block of that function. Function: Labels can be used anywhere in the function in which they are declared. Only labels have function scope. File: A name declared outside all blocks and classes has file scope and can be used in the translation unit in which it is declared after the point of declaration. Names declared with file scope are said to be global. Class:The name of a class member is local to its class and can be used only in a member function of that class, after the . operator applied to an object of its class or a class derived from its class, after the -> operator applied to a pointer to an object of its class or a class derived from its class, or after the ::scope resolution operator applied to the name of its class or a class derived from its class. A name first declared by a friend declaration belongs to the same scope as the class containing the friend declaration. A class first declared in a return or argument type belongs to the global scope.

123 const int Arraysize = 12; // default size3.8 Class Templates A container class is one that operates on a collection of 0 or more objects of a particular type. For example, a linked list is a container class. So is an array. If we wish to use an Array class of integer, doubles, characters, Complex numbers, BitVectors, or Strings, we have to implement each class and give them unique name since class names cannot be overloaded. const int Arraysize = 12; // default size class IntArray { public: IntArray (int sz = ArraySize); IntArray (const int*, int); IntArray (const IntArray&); ~IntArray() {delete [] ia; } IntArray& operator= (const IntArray&); int& operator[](int); int getSize() { return size; } protected: void init(const int*, int); int size; int *ia; };

124 The C++ template facility also provides for the automatic generation of class instances bound to a particular type. template class Array { public: Array(int sz = 12) : ia(new type[sz]), size(sz) {} ~Array() {delete ia;} private: type *ia; int size; }; Array ia; Array ic; Array is; Similary, we can define other container class as follows:

125 A template queue class A queue is a datat structure in which items are entered at one end, the back, and removed at the other end, the front. The operations upon a queue const of the following: void add(item); item remove(); Boolean is_empty; Boolean is_full(); The implementation of a Queue is presented in the following sections to illustrate the definition and use of template class. The Queue is implemented as a pair of class abstraction: 1. The Queue itself, providing the public interface and a pair of data member: front and back. The Queue is implemented as a linked list. 2. A QueueItem. Each item intered into the Queue is represented by a QueueItem. A QueueItem contains a value and a link to the next QueueItem. The actual type of value varies with each instantiation of a Queue.

126 Template Class Definition1. The template keyword begins every forward declaration and definition of a template class. 2. It is followed by a formal template parameter list surrounded by angle brackets. 3. The formal parameter list cannot be empty. 4. Multiple parameters are separated by a comma. 5. A class may also declare expression parameters.

127 Definition of QueueItem template class:template class QueueItem { public: QueueItem (const Type&); private: Type item; QueueItem *next; }; Each occurrence of the QueueItem class name within the class definition is a shorthand notation for QueueItem Outside the class definition, the programmer must make the parameter list explicit: inline QueueItem:: QueueItem( const Type &t) : item(t) / { next = 0; } To create a QueueItem class of integer or strings:

128 Whenever the template class name is used as a type specifier in the context of a template definition, the full parameter list must be specified: template < class Type> void display (QueueItem &qi) { QueueItem *pqi = &qi; // ... }; The generation of an integer or String QueueItem class is spoken of as an instantiation. Each occurrence of the formal parameter is replaced by the actual type of the instantiation. The String QueueItem class literally becomes: class QueueItem{ public: QueueItem( const String& ); private: String item; QueueItem *next;

129 What is the difference between the following two friend declarations:(1) template class QueueItem { template< class T> friend class Queue; // ... } (2) class QueueItem{ friend class Queue; The first declaration declars all possible Queue instances to be friends to each QueueItem instantiation. For example, a Queue of Strings is a friend of a integer QueueItem. (It makes no sense in this example). The first declaration declars that every instantiation of QueueItem to a particular type, the corresponding Queue instantiation is its friend.

130 Here is our definition of the Queue template class.#ifndef Queue_H #define Queue_H enum Boolean { false=0, true}; // forward declaration of QueueItem template class QueueItem; template class Queue { public: Queue() { front = back = 0; } ~Queue(); Type remove(); void add(const Type&); Boolean is_empty() { return front == 0 ? true: false; } private: QueueItem *front; QueueItem *back; }; #endif

131 template Queue::~Queue() { while (is_empty() != true) (void) remove(); } void Queue::add(const Type &val) { // allocate a new QueueItem object QueueItem *pt = new QueueItem (val); if (is_empty()) front = back = pt; else { back->next = pt; back = pt; } } #include #include Type Queue::remove() { if (is_empty() == true){ cerr << "remove() on empty queue\n"; exit(-1); } QueueItem *pt = front; front = front ->next; Type retval = pt->item; delete pt; return retval; }

132 A user may need the ability to display the Queue's content.Again, there are two alternative way to implement: (1) ostream& operator<<(ostream&, Queue&); ostream& operator<<(ostream&, Queue&); ostream& operator<<(ostream&, Queue&); // ... (2) template ostream& operator<<(ostream&, Queue&); Here is one possible implementation of the output operator for a Queue: ostream& operator<<(ostream &os, Queue &q) { os << "<" QueueItem *p; for (p=q.front; p; p=p->next) // must define operator<< for QueueItem os << *p <, " "; os << ">"; return os; } If a Queue of integer contains the value 7,5,3,3,9,6, and 7, what is the output for the above program?

133 The next thing we need to do is to declare the operator << as a friend to Queue. What's wrong with the following declaration? template class Queue { template friend ostream& operator<< (ostream&, Queue&); // ... }; The declaration makes all instances of the output operator a friend to each Queue instantiation. Rather, we'd like a one-to-one mapping of friendship between a Queue and operator instance for each instantiated type. friend ostresm& operator<<(ostream&, Queue &); The actual display of the Queue elements is pushed back onto the QueueItem output operator. So, the output operator also needs to be implemented (as a template function) for QueueItem (and also for the item in the QueueItem if the type of item is a user-defined type).

134 What is the output for the following program:#include #include "Queue.c" main() { Queue *p_qi = new Queue; cout << *p_qi << endl; int ival; for (ival = 10; ival <20; ++ival) p_qi->add(ival/3); int err_cnt = 0; for(ival = 10; ival < 20; ++ival){ int qval = p_qi->remove(); if((int)(ival/3) !=qval) err_cnt++; } cout << **p_qi << endl; if (!err_cnt) cout << "!! queue executed OK\n"; else cout << "?? queue errors: "<< err_cnt << endl; return 0; }

135 Template Class SpecializationThere are particular types for which a default template member function is not sufficient. In these case, the programmer can provide an explicit implementation to hanle a particular type. For example, we would like to write a template class for points (grid points, real points and rational points, defines as classes g_points, f_points and r_points, respectively) template class point {/* ... */ }; The implementation of operator * are similar for point and point, so we can define this operation using template: point& point::operator*(const point&) const; However, we have to write another function for the rational points because the computation for the multiplication of rational points is different. point& point::operator*(const point&) const;

136 3.9 Example: A Template Array Class#ifndef ARRAY_H #define ARRAY_H #include template class Array; template ostream& operator<<(ostream&,Array&); const int ArraySize = 12; class Array { public: Array(int sz=ArraySize) {ia = new Type[size=sz]; assert(ia!=0); } Array(const Type *ar, int sz){ init(ar,sz); } Array(const Array &iA) {init(iA.ia, IA.size); ~Array(){delete [] ia; } Array& operator=(const Array&); int getSize() {return size; } void grow(); void print(ostream& = cout); Type& operator[](int ix) {return ia[ix]; } void sort(int, int); int find(Type); Type in(); Type max(); private: void swap(int,int); void init(const Type*, int); int size; Type *ia; }; #endif

137 template ostream& operator<<(ostream& os, Array& ar) { ar.print(os); return os; } template void Array::print(ostream& os) const lineLength = 12 ; os << "( " << size << " )< "; for ( int ix = 0 ; ix < size ; ++ix) { if (ix % lineLength==0 && ix) os << "\n\t"; os << ia[ix]; //don't generate comma for last item on line //nor for the last element of the array if (ix % lineLength != lineLength-1 && ix != size-1) os<< ", "; os << " >\n"; Example comes from the text book page 380

138 template Array&Array::operator=( const Array &iA) { if (this == &iA) return *this; delete [ ] ia; init( iA.ia, iA.size ); return *this ; } #include template void Array::init(const Type *array, int sz) ia = new Type[size = sz] ; assert ( ia != 0 ); for (int ix = 0 ; ix < size ; ++ix) ia[ix] = array[ix] ; Array::grow() Type *oldia = ia ; int oldSize = size; int newSize = oldSize + oldSize/2 + 1; ia = new Type[size=newSize]; assert(ia != 0); for (int i = 0; i ia[i] = oldia[i]; delete [] oldia ;

139 template Type Array::min() { assert( ia != 0); Type min_val = ia[0]; for (int ix=1; ix if (min_val > ia[ix]) min_val = ia[ix]; return min_val ; } Type Array::max() assert(ia != 0) ; Type max_val = ia[0]; for (int ix=1; ix if (max_val return max_val; int Array::find(Type val) for (int ix=0; ix if (val==ia[ix]) return ix ; return -1 ;

140 template void Array::swap(int i, int j) { Type tmp = ia[i]; ia[i] = ia[j]; ia[j] = tmp ; } void Array::sort(int low, int high) if (low >= high) return; int lo = low; int hi = high + 1; Type elem = ia[low]; for ( ; ; ) { while (ia[++lo] < elem) ; while(ia[--hi] > elem) ; if ( lo < hi ) swap(lo,hi) ; else break; swap(low,hi); sort(low,hi-1); sort(hi+1,high);

141 #include "Array.h" template void try_array( Array &iA ) { cout << "try_array: initial array values:\n"; cout << iA << endl; Type find_val = iA[iA.getSize() - 1]; iA[iA.getSize()-1] = iA.min(); int mid = iA.getSize()/2; iA[0] = iA.max() ; iA[mid] = iA[0] ; cout << "try_array:after assignments:\n"; cout << iA << endl ; Array iA2 = iA; iA2[mid/2] = iA2[mid]; cout << "try_array: memberwise initialization \n" ; iA = iA2; cout << "try_array: after memberwise copy\n"; iA.grow(); cout << "try_array: after grow\n" ; int index = iA.find(find_val); cout << "value to find: " << find_val; cout << "\tindex returned: " << index << endl; Type value = iA[index] ; cout << " value found at index: "; cout << value << endl; }

142 #include "Array.c" #include "try_array.c" #include "String.h" main() { static int ia[] = {12,7,14,9,128,17,6,3,27,5}; static double da[] = {12.3,7.9,14.6,9.8,128.0}; static String sa[] = { "Eeyore", "Pooh", "Tigger", "Piglet", "Owl", "Gopher","Heffalump" }; Array iA(ia,sizeof(ia)/sizeof(int)) Array dA(da,sizeof(da)/sizeof(double)); Array SA(sa,sizeof(sa)/sizeof(String)); cout << "template Array class\n" << endl; try_array(iA); cout << "template Array class\n" << endl; try_array(dA); cout << "template Array class\n" << endl; try_array(SA); return 0; }

143 Chapter 4 Class Derivation and Inheritance4.1 Introduction 4.2 Derivation Specification 4.3 Information Hiding Under Derivation 4.4 Public, Protected, and Private Base Classes 4.5 Virtual Functions 4.6 Initialization and Assignment under Derivation (will add) 4.7 Standard Conversions Under Derivation (WILL ADD) 4.8 Class Scope Under Derivation 4.9 4.? Example for Derived Class:Page or Section 6.4 Stroupstrup

144 4.1 Introduction Object-oriented programming extends abstract data types to allow for type/subtype relationships. This achieved through a mechanism referred to as inheritance. Rather than reimplementing shared characteristics, a class can inherit selected data members and member functions of other class. In C++, inheritance is implemented through the mechanism of class derivation. Class inheritance allows the members of one class to be used as if they were members of a second class. For example, a member of a class "shape" should be also a member of the classs "circle" or "tirangle". E.g. class shape{ private: int pen_color; int pen_thickness; public: inline void whatcolor(){return pen_color}; // }

145 class point2D{ float x,y; // } class circle : public shape{ point2D center; float radius; void circle(point2D, float, int, int); // } circle::circle(point2D p, float r, int color, int thick){ center = p; radius = r; shape::pen_color = color; shape::pen_thickness = thick; // ..... } main(){ point2D p(1.0,2.0); circle c(p,3.0,RED,NORMAL); cout <

146 An information center of a zoo try to installing display terminals to answer questions posed by visitors about their animals. We are asked to design a C++ program for them using class derivation. (page 394 in taxt book) The zoo animals exist at different levels of abstraction. There are individual animals, such as Ling-ling (a famous panda ,as a gift from China to USA). Each animal belongs to a species; Ling-ling, for example, is a giant panda. Species in turn are members of families. A giant penda is a member of the bear family. Each family in turn is a member of the animal kingdom - in this case, the more limited kingdom of a particular zoo. The taxonomy of the zoo animals maps nicely into an inheritance hierarchy. It constructs a "tree" hierarchy, that is, each derived class has only one immediate base class. This inheritance hierarchy is referred as single inheritance.

147 The taxonomy of the zoo animals does not provide a complete representation. For example, Panda is a species of Bear. However, it is also an endangered species, although the Polar and Grizzly Bear species are not. The Leopard species of the Cat family is also endangered. Multiple inheritance defines a relationship between independent class type. The derived class can be though of as a composite of its multiple base classes. The multiple inheritance constructs a "DAG" hierarchy. C++ supports both single and multiple inheritance.

148 The figure below illustrates three levels of a zoo animal derivationThe figure below illustrates three levels of a zoo animal derivation. The ZooAnimal class, referred to as an abstract base class, is designed specifically as a class from which other classes can be derived. It can be though of as an incomplete class that is more or less finished with each subsequent derivation. So, actual class objects of ZooAnimal do not actually exit -- only their derived class instances are created in an actual application.

149 4.2 Derivation SpecificationThe skeletal implementation for the figure in previous page looks as follows: class ZooAnimal {}; class Endangered {}; class Carnivore {}; class Herbivore {}; class Bear : public ZooAnimal {}; class Cat: public ZooAnimal, Carnivore {}; class Panda : private Endangered, public Bear, private Herbivore {}; Panda Ling_ling; A derived class may itself serve as a base class in a subsequent derivation. Bear, for example, derived from ZooAnimal, serves as a public base class of Panda.

150 The syntax for defining a base class is the same as that of an "ordinary" class with two exception:1. Members intended to be inherited but not intended to be pulbic are declared as protected members. 2. Member function whose implementation depends on representational details of subsequent derivations that are unknown at the time of the base class design are declared as virtual functions. class ZooAnimal { public: ZooAnimal(char*, char*, short); virtual ~ZooAnimal(); virtual void draw(); void locate (); void inform(); protected: char *name; char *infoFile; short location; short count; }

151 Definition of a Derived Class#include "ZooAnimal.h" class Bear : Public ZooAnimal { public: Bear(char*, char*, short, char, char); ~Bear(); void locate(int); int isOnDisplay(); protected: char beginFed; char isDanger; char onDisplay; char epoch; } The colon following the class tag name indicates the presence of a class derivation list, a (possibly) comma-separated list of one or more base classes. 1. No class name may appear more than once. 2. Each listed base class must have been defined. 3. If no access keyword (public, protected, or private) specified, the base class by default becomes privates. (the meaning of access keyword will described later).

152 Inherit Member Access The inherited ZooAnimal members can be accessed as if they were members of Bear. void objectExample(Bear& ursus) { if( ursus.isOnDisplay()) { ursus.locate(low_intensity);// enum constant if (ursus.beginFed) cout << ursus.name << "is now being fed\n"; ursus.inform(); } In most cases, use of the class scope operator is redundant. In two cases, however, this additional aid is necessary: 1. When an inherited member's name is reused in the derived class. 2. When two or more base classes define an inherited member with the same name.

153 Base Class InitializationThe member initialization list is used to pass arguments to a base class constructor. The tag name of a base class is specified, followed by its argument list enclosed in parentheses. Bear::Bear(char *nm, char *fil, short loc, char danger, char age) : ZooAnimal (nm, fil, loc) // single base class { epoch = age; isDanger = danger; } Each base class may be listed in turn in the case of multiple base classes. Panda::Panda(char *nm, short loc, char sex) : Endangered(CHINA),// constants defined elsewhere Herbivore(BAMBOO), Bear("Ailuropoda melaoleuca", "Panda", 0, PANDA, MIOCENE) { name = new char[strlen(nm) +1]; strcpy(name, nm); cell = loc; gender = sex; }

154 4.3 Information Hiding Under Derivation A protected class member is public to the member functions and friends of a derived class; it is private to the rest of the program. class ZooAnimal { public: int isNowFeeding() {return beginFed; } protected: int beginFed; // }; class Bear : public ZooAnimal { void activities (); // ..... void checkFeeding(); // sets beginFed void Bear::activities(){ checkFeeding(); } void Bear::checkFeeding(){ beginFed=1; } // determine if Bear is now being fed main(){ Bear yogi; // Both compiler errors: illegal access of nonpublic members While(Yogi.biginFed == 0) yogi.checkFeeding(); }

155 (1) A derived class has no access privilege to the private members of a base class.class ZooAnimal { friendd void setPrice (ZooAnimal&); public: isOnDisplay(); protected: char *name; char onDisplay; private: char forSale; }; class Primate : public ZooAnimal { friend void canCommunicate(Primate*); locate(); short zooArea; char languageSkills; } We denote Primateaccess = ZooAnimal(protected), which means the member of Private has access privilege higher than or equal to "protected". With similar notation, a function's (or program's) access privilege can be defined. E.g. mainaccess = ZooAnimal(public);

156 void setPrice (ZooAnimal &z) {(2) A friend function has the same access privilege as the member function of that class. void setPrice (ZooAnimal &z) { Primate *pr; if (pr->forSale && pr->languageSkills) // } void canCommunicate (Primate *pr) { ZooAnimal za; if (pr->onDisplay && pr->forSale && za.onDisplay

157 (3) The derived class has no special access privilege to objects of its base class. Rather, the derived class has access privilege to the nonprivate inherited members of a derived class object. Primate::locate() { ZooAnimal za; Primate pr; if (onDisplay && pr.onDisplay && za.onDisplay // } Derivation is not friendship. Derivation provides for type extension. Primate is a specialized instance of a ZooAnimal. It shares the characteristics of a ZooAnimal, but adds a set of attributes that apply only to itself. Friendship provides for data access of otherwise nonpublic members. It does not define a type relationship. Derivation is not a special form of friendship -- one that provides access to the protected but not private members of individual base class objects. Only the friends and member function of ZooAnimal, for example, can access the nonpublic members of a ZooAnimal class object.

158 4.4 Public, Protected, and Private Base Classes(1) Public: The inherited members of a public base class maintain their access level within the derived class. (2) Protected: The inherited public and protected members of a protected base class become protected members of the derived class. (3) Private: The inherited public and protected members of a private derivation become private members of the derived class. Base Public Protected Private Derived Public Protected Private

159 The protected and private base class have two significant efficts:1. The inherited public interface of the hierarchy cannot be accessed by the general program through instances of a class with a nonpublic derivation. class ZooAnimal { public: void locate(); void inform(); // }; class Bear : public ZooAnimal {}; class ToyAnimal : private ZooAnimall { protected: void where_is_it() { locate(); } }; main(){ Bear yogi; ToyAnimal pooh; yogi.inform(); pooh.inform(); // }

160 2. There is no implicit conversion within the general program of a derived class to its nonpublic base class. An explicit cast by the programmer is necessary. extern void draw( ZooAnimal *pz){ px->draw();} main(){ Bear fozzie; ToyAnimal eeyore; draw(&fozzie); draw(&eeyore); draw((ZooAnimal *) &eeyore); ZooAnimal *pz = &eeyore; pz = (ZooAnimal *) &eeyore; // ... }

161 Protected Base Class // All nonprivate members of ZooAnimal become // protected members of Rodent. This permits them // to be accessed by all subsequent class derivations // while prohibiting the general program from having // access to them. class Rodent : protected ZooAnimal { public: virtual void assuringMessage(); protected: virtual void reportSightings(ZooLoc); unsigned long howMany; // }; class Rat : public Rodent { // ... void log() { inform(); } };

162 main() { Bear anyBear; Rat anyRat; anyBear.inform(); anyRat.inform(); anyRat.assuringMessage(); // } There is no standard conversion between a derived class and its nonpublic base class except within the scope of the derived class. extern void draw(ZooAnimal *); Rat::loc(){ Rat ratso; draw(&ratso); } draw(&ratso); }

163 Private Base Class #ifndef STACK_H #define STACK_H typedef int Type; const int BOS = -1; // Bottom Of Stack const int stack_size = 24; class Stack { public: Stack(int sz = stack_size); ~Stack(); is_empty() { return top == BOS; } is_full() { return top == size - 1; } void push (Type value); Type pop(); private: int top; int size; Type *array; // use array of Type to represent a // stack }; #endif

164 #ifndef ARRAY_H #define ARRAY_H #include template class Array; template ostream& operator<<(ostream&, Array&); const int ArraySize = 12; template class Array { public: Array(int sz=ArraySize) {ia = new Type[size=sz]; assert(ia!=0); } Array(const Type *ar, int sz){init(ar,sz); } Array(const Array &iA) {init(ar,sz); } ~Array () { delete [] ia; } Array& operator=(const Array&); int getSize() {return size; } void grow(); void print(ostream& = cout); Type& operator[](int ix) {return ia[ix]; } void sort(int, int); int find(Type); Type min(); Type max(); private: void swap(int, int); void init(const Type*, int); int size; Type *ia; }; #endif Array ia(4); Array da(10);

165 What we'd really like is a fully guaranteed (that is, tsted and supported) implementation of an array (or linked list, if a list class available) that we can plug into our Stack class. This frees us to concentrate on getting the stack representation correct. #include "Array.h" const int BOS=-1; // Bottom of Stack const int StackSize = ArraySize; // in Array.h template class Stack : public Array { public: Stack(int sz=StackSize): Array(sz),top(BOS){} int is_empty(){return top == BOS;} int if_full() {return top == size-1; } void push(Type value) { if(is_full()) /* error handling */ ; ia[++top] = value; } Type pop(){ if(is_empty()) /* error handling */ ; return ia[top--]; } private: int top; };

166 Notice that it is inappropriately to use Array a public base class.template extern void swap(Array&, int, int); Stack is; // oops: unexpected misuses of a Stack swap(is,i,j); is.sort(); is[0] = is[1]; If we change the public base class Array into private base class. That is, we replace the public keyword with that of private: class Stack: private Array { }; The entire public interface of the base class (Array) becomes private in the derived class (Stack). // illegal under private derivation

167 4.5 Virtual Functions A virtual function is a special member function invoked through a public base class reference or pointer; it is bound dynamically at run time. /* nonobject-oriented implementation: burden of type * resolution is on programmer code requires * knowledge of type representation it must be changed * with each change to that type representation */ void finalCollage(ZooAnimal *pz){ for(ZooAnimal *p = pz; p; p=p->next) switch(p=>isA()){ case BEAR: ((Bear *) p)->draw(); break; case PANDA: ((Panda *) p)->draw(); // ... every other derived class } } void finalCollage(ZooAnimal *pz) { for (ZooAnimal *p=pz; p; p=p->next) p->draw();} // dynamic binding at run time.

168 A virtual function is specified by prefacing a function declaration with the keyword virtual. Only class member functions may be declared as virtual. #include class ZooAnimal { public: ZooAnimal(char *WhatIs = "ZooAnimal") : isa(whatIs) {} void isA() {cout <<"\n\t" << isa << "\n"; } void setOpen(int status) {isOpen=status; } vitual int isOnDisplay() {retuen isOpen; } virtual void debug(); vitrual void draw() = 0; protected: vitrual void locate() = 0; char *isa; char isOpen; }; viod ZooAnimal::debug(){ isA(); cout << "\tisOpen: " << ((isOnDisplay()) ? "yes" : "no") << endl; }

169 The member functions debug(), locate(), draw(), and isOnDisplay() are declared as virtual functions because the actual implementation details are dependent on the class type and are not known at this time. Virtual functions defined in the base class of the hierarchy are often never intended to be invoked, as in the case with locate() and draw(). These two member functions are spoken of as pure virtual functions. The class designer can indicated that a virtual function is undefined for an abstract class by initializing its declaration to 0. The class that first declares a function as virtual must either declare it as a pure virtual function (such as draw() and locate()) or provide a definition (such as isDisplay()). If a definition is provided, it serves as a default instance for a subsequent class derivation should the derived class choose not to provide its own instance of the virtual function. If a pure virtual function is declared, the derived class can either define an instance of the function or by default inherit the pure virtual function of its base class. If the class inherits a pure virtual function, it is treated as an abstract class; no objects of the class may exist within the program.

170 What if we wish to defer implementation of draw() until a particular species, such as Panda or Grizzly, is derived? Here are three alternative solutions: 1. Define a null instance of the virtual function: class Bear : public ZooAnimal { public: void draw() {} // } 2. Define an instance whose invocation results in an internal error. void Bear::draw(){ error(INTERNAL, isa, "draw()"); } 3. Define an instance to log the unexpected behavior, while drawing a generic image of a Bear. That is, keep the system running, but also keep a record of run-time exceptions that need to be handled sometime in the future.

171 The following example comes from chapter 13 of the book: 4.6 Example of C++ class: The following example comes from chapter 13 of the book: C++ Components and Algorithms by Scott Robert Ladd. /////////////////////////////////////////////////////////////// // PERSISTENCE LIBRARY // bintree.h // Binary tree class for Persistent objects // Copyright 1992 Scott Robert Ladd // All rights reserved #ifndef BINTREE_H #define BINTREE_H #include "persist.h" // // TreeErrorBase // Base class providing error handling for Tree classes class TreeErrorBase { public: static void SetErrOut(const ErrReporter & er); protected: static ErrReporter * ErrOut; static void ReportError(); }; /* The class TreeErrorBase will be illustrated in the Error Handling section in the future */

172 //-------------------------------------------------------------// TreeNode // A node in a binary tree struct TreeNode : public TreeErrorBase { // links TreeNode * Less; TreeNode * Greater; TreeNode * Parent; // contents KeyString Key; DataBlock Data; // constructor TreeNode(const KeyString & k, const DataBlock & db); // copy constructor TreeNode(const TreeNode & node); // assignment operator void operator = (const TreeNode & node); };

173 //-------------------------------------------------------------// BinaryTree // A basic binary tree typedef Boolean (* TreeEnumFunc)(const KeyString & str, const DataBlock & db); class BinaryTree : public TreeErrorBase { public: // constructor BinaryTree(); // copy constructor BinaryTree(const BinaryTree & tree); // destructor ~BinaryTree(); // assignment opeartor void operator = (const BinaryTree & tree); // store an item Boolean Insert(const KeyString & key, const DataBlock & db); // delete an item Boolean Delete(const KeyString & key); // retrieve an item DataBlock LookUp(const KeyString & key) const; // traverse entire tree, calling a function for each node void Enumerate(TreeEnumFunc func); protected: // data members TreeNode * Root; // root node TreeEnumFunc EnumFunc; // pointer to enumeration function // recursive copy function void RecursiveCopy(TreeNode * node); // recursive traversal function void RecurseTraverse(TreeNode * node); // recursive deletion function void RecursiveDelete(TreeNode * node); }; #endif

174 ///////////////////////////////////////////////////////////////// PERSISTENCE LIBRARY // bintree.cxx // Binary tree class for Persistent objects // Copyright 1992 Scott Robert Ladd // All rights reserved #include "stddef.h" #include "stdlib.h" #include "bintree.h" // // TreeErrorBase // Base class providing error handling for Tree classes ErrReporter * TreeErrorBase::ErrOut = NULL; void TreeErrorBase::ReportError() { if (ErrOut != NULL) ErrOut->Fatal("memory allocation failure in tree"); } void TreeErrorBase::SetErrOut(const ErrReporter & er) { if (ErrOut != NULL) delete ErrOut; ErrOut = new ErrReporter(er); } // TreeNode // A node in a binary tree // constructor TreeNode::TreeNode(const KeyString & k, const DataBlock & db) : Key(k), Data(db) { Parent = NULL; Less = NULL; Greater = NULL; }

175 // copy constructor TreeNode::TreeNode(const TreeNode & node) : Key(node.Key), Data(node.Data) { Parent = node.Parent; Less = node.Less; Greater = node.Greater; } // assignment operator void TreeNode::operator = (const TreeNode & node) Key = node.Key; Data = node.Data; // // BinaryTree // A basic binary tree // constructor BinaryTree::BinaryTree() { Root = NULL; } BinaryTree::BinaryTree(const BinaryTree & tree) { Root = NULL; RecursiveCopy(tree.Root); } // destructor BinaryTree::~BinaryTree() { RecursiveDelete(Root); }

176 // assignment opeartorvoid BinaryTree::operator = (const BinaryTree & tree) { RecursiveDelete(Root); Root = NULL; RecursiveCopy(tree.Root); } // retrieve an item DataBlock BinaryTree::LookUp(const KeyString & key) const { TreeNode * node = Root; while (node != NULL) { if (key == node->Key) break; if (key < node->Key) node = node->Less; else node = node->Greater; } if (node == NULL) return NULL_BLOCK; else return node->Data; // traverse entire tree, calling a function for each node void BinaryTree::Enumerate(TreeEnumFunc func) { EnumFunc = func; RecurseTraverse(Root); } // recursive copy function void BinaryTree::RecursiveCopy(TreeNode * node) { if (node != NULL) { Insert(node->Key,node->Data); RecursiveCopy(node->Less); RecursiveCopy(node->Greater);

177 // store an item Boolean BinaryTree::Insert(const KeyString & key, const DataBlock & db) { Boolean result = BOOL_FALSE; TreeNode * newnode = new TreeNode(key,db); if (newnode == NULL) ReportError(); if (Root == NULL) { Root = newnode; result = BOOL_TRUE; } else { TreeNode * node = Root; while (node != NULL) { if (newnode->Key == node->Key) {// replace a duplicate key newnode->Less = node->Less; // copy links from old node newnode->Greater = node->Greater; newnode->Parent = node->Parent; if (node == Root) // is node the root? Root = newnode; // replace root node else { // replace node with newnode in parent if (node->Parent->Less == node) node->Parent->Less = newnode; else node->Parent->Greater = newnode; } delete node; // delete old node break; } if (newnode->Key < node->Key) { if (node->Less == NULL) { // insert node node->Less = newnode; newnode->Parent = node; } else node = node->Less; // move to next node } else { if (node->Greater == NULL) { node->Greater = newnode; // insert node } else node = node->Greater; // move to next node return result;

178 // delete an item Boolean BinaryTree::Delete(const KeyString & key) { TreeNode * node = Root; while (node != NULL) { if (key == node->Key) break; if (key < node->Key) node = node->Less; else node = node->Greater; } if (node == NULL) return BOOL_FALSE; if (node->Greater == NULL) { if (node->Less == NULL) { if (node == Root) Root = NULL; // tree is now empty! else { // remove leaf node if (node->Parent->Less == node)node->Parent->Less = NULL; else node->Parent->Greater = NULL; else // node has a "lesser" subtree { if (node == Root) Root = node->Less; { // splice "less" subtree if (node->Parent->Less == node) node->Parent->Less = node->Less; else node->Parent->Greater = node->Less; else // node has a "greater" subtree { if (node == Root) Root = node->Greater; // new root node { // splice "greater" subtree if (node->Parent->Less == node) node->Parent->Less = node->Greater; else node->Parent->Greater = node->Greater;

179 else // deleted node has two decendants... ugh!{ // look for immediate successor TreeNode * successor = node->Greater; while (successor->Less != NULL) successor = successor->Less; // unlink successor from tree if (successor->Parent->Less == successor) successor->Parent->Less = successor->Greater; else successor->Parent->Greater = successor->Greater; // copy data from successor to deleted node node->Key = successor->Key; node->Data = successor->Data; // update parent links in children if (successor->Greater != NULL) successor->Greater->Parent = node; // set successor to be deleted node = successor; } // delete node that was removed delete node; return BOOL_TRUE; // recursive traversal method void BinaryTree::RecurseTraverse(TreeNode * node) { if (node != NULL) { RecurseTraverse(node->Less); EnumFunc(node->Key,node->Data); RecurseTraverse(node->Greater); } } // recursive deletion method void BinaryTree::RecursiveDelete(TreeNode * node) { if (node != NULL) { RecursiveDelete(node->Less); RecursiveDelete(node->Greater); delete node; } }

180 Chapter 5 Object-Oriented Design and Object-Oriented Analysis5.1 Object-Oriented Methodology -- Object Modeling Technique 5.2 Object Model 5.3 Dynamic Model 5.4 Function Model 5.5Analysis 5.6 Example

181 Object-oriented means that we organize software as a collection of discrete objects that incorporate both data structure and behavior. data structure hierarchy is replaced by Conventional procedural approach Object-oriented class hierarchy

182 Characteristic of Objects1. Identity -- The data is quantized into discrete, distinguishable entities called objects. 2. Classification -- The object with the same data structure (attributes) and behavior (opeerations) are group into a class. 3. Polymorphism -- The same operation may behave differently on different classes. 4. Inheritance -- Inheritance is the sharing of attributes and operations among classes based on a hierarchical relationship.

183 Object-Oriented Themes1. Abstraction 2. Encapsulation (Information hinding) 3. Combining data structure and behavior 4. Sharing 5. Emphasis on object structure, not prucedure structure 6. Synergy

184 Object-Oriented Development (OOD)OOD is a conceptual process independent of a programming language until the final stage. OOD is fundamentally a new way of thinking and not a programming technique. The greastest benefits of OOD comes from helping specifiers, developers, and customers express abstract concepts clearly and communicate them to each other.

185 Object-Oriented Methodology --Object Modeling Technique1. Analysis 2. System design 3. Object design 4. Implementation

186 Object Modeling Technique (OMT)1. Analysis Starting from a statement of the problem, the analyst builds a model of the real-world situation showing its important properties. The analysis model is a concise, precise abstraction of what the desire system must do, not how it will be done. 2. System-Design System Design is the high-level strategy for solving the problem and building a solution. System Design includes: (a) decisions about the organization of the system into subsystemms. (b) the allocation of subsystems to hardware and software components. (c) major conceptual and policy decisions that form the framework for detailed design.

187 3. Object-design The object designer builds a design model based on the analysis model but containing implementation details. 4. Implementation The object classes and relationships developed during object design are finally translated into a particular programming language, database, or hardware implementation.

188 Model What is a model? A model is an abstraction of something for the purpose of understanding it before building it. Why we use model? A model omits nonessential details, it is easier to manipulate than the original entity. Models serve several purposes: 1. Testing a physical entity before building it. 2. Communication with customers. 3. Visualization. 4. Reduction of Complexity.

189 Build Complex Systems To build complex systems, the developer must: 1. Abstract different views of the system. 2. Build models using precise notation. 3. Verify that the models satifsy the requirements of the system. 4. Gradually add detail to transform the models into an implementation.

190 OMT Model OMT is the methodology that combines three views of modeling system: 1. Object model describes the objects in a system and their relationships (object diagram). 2. Dynamic model describes the interactions among objects in a system(state diagram). 3. Functional model describes the data transformation of the system (data flow diagram).

191 OMT Model A typical software procedure incorporates three aspects: 1. It uses data structures (object model). 2. It sequences operations in time (dynamic model). 3. It transforms values (functional model).

192 Object Model An object is simply something that makes scence in an application context. (Person) Joe Smith (Person) Mary Sharp (Person) Object Instances (Class Name) attribute_name=value Objects (Class Name) (Person) Joe Smith 24 (Person) Mary Sharp 52 Objects with Values

193 Object Model An object class describes a group of objects with similar properties (attributes), common behavior (operators), common relationships to other objects and common semantics. Class Class Name Class Name attribute attribute:datatype attribute = init_value ...... operation operation (arg_list) : return_type ...... Person Class Person name:string age:integer Class with Attributes

194 Object Model An operation is a function or transformation that may be applied to or by objects in a class. An method is the implementation of an operation of an operation for a class. Person name age change-job change-address File file name size in bytes last update Geometric object color position move (delta: Vector) select (p : Point): Boolean rotate (angle

195 Object Model A link is a physical or conceptual connection between object instance. A association describes a group of links with common structure and common semantics . Association Association Name Class-1 Class-2 role-1 role-2 Has-capital Country name City name Class diagram (Country) Canada Has-capital (City) Ottawa (Country) France Has-capital (City) Paris Instance diagram (Country) Senegal Has-capital (City) Dakar

196 Associations may be binary, ternary, or higher order.Object Model Associations may be binary, ternary, or higher order. Ternary Association Association Name Class-1 Class-2 role-1 role-2 role-3 Class-3 Project Language Class diagram Person (Project) accounting system (Language) Cobol Instance diagram (Person) Mary (Project) CAD program (Language) C

197 Object Model A role is one end of an association. Person Companyemployee employer Work-for employee employer Joe Doe Simplex Mary Brown Simplex Jean Smith United Widgets

198 Object Model Multiplicity specifies how many instances of one class may relate to a single instance of an associated class. Multiplicity of Associations Class Exactly one Many (zero or more) Optional(zero or one) One or more Numerically specified 1+ 1-2, 4

199 Object Model Many-to-many association and links. Intersects Line PointClass diagram 2+ name name (Line) L1 (Line) L2 (Point) P1 Instance diagram (Line) L3 (Point) P2 (Line) L4 (Line) L5 L2 L3 P2 Sample data P1 L5 L4 L1

200 A link attribute is a property of the links in an association.Object Model A link attribute is a property of the links in an association. Link Attribute: Accessible by Class-1 User link attribute Accessible by File User access permission /etc/termcap (read) John Doe /etc/termcap (read-write) Mary Brown /usr/doe/.login (read-write) John Doe

201 Object Model Link aattributes for one-to-many associations and a tenary association. Works-for Person Company name social security no. address name address boss salary job title Manages worker performance rating Team Pitcher Year wins losses Harry Eisenstat Cleveland Indians Harry Eisenstat Detroit Tigers Willis Hudlin Cleveland Indians Willis Hudlin Cleveland Indians Willis Hudlin Washington Senators Willis Hudlin St.Louis Browns

202 Object Model Link attribute versus object attribute. Preferred form.Works-for Company Person Preferred form. name social security no. address name address salary job title Works-for Company Person name social security no. address salary job title name address Discouraged form.

203 The Object on the "many" side of an association have explicit order .Object Model The Object on the "many" side of an association have explicit order . Ordering: {ordered} Class {ordered} Window Screen Visible-on

204 Object Model A qualified association relates two object classes and a qualifier. The qualifier is a special attribute that reduces the effective multiplicity of an association. Qualified Association: Association Name Class-1 qualifier Class-2 role-1 role-2 Directory file name File

205 Object Model Aggregation is the "part-whole" or "a-part-of" relationship in which objects representing the components of something are associated with an object representing the entire assembly. Aggregation: Aggregation(alternate form): Assembly Class Assembly Class Part-1-Class Part-2-Class Part-1-Class Part-2-Class Microcomputer 1+ System box Monitor Keybord Mouse Chassis CPU RAM Fan

206 Object Model Generalization and Inheritance are powerful abstractions for sharing similarities among classes while preserving their differences. Generalization (Inheritance): Superclass Subclass-1 Subclass-2

207 Inheritance for graphic figuresObject Model Inheritance for graphic figures Figure color center position pen thickness pen type move select rotate display 0 Dimensional 1 Dimensional 2 Dimensional orientation fill type orientation scale fill scale Point Line Arc Spline Polygon Circle num of sides vertices endpoints control pts diameter radius start angle arc angle display display display display rotate display

208 Object Model R eview Ternary Association Association Name Class-1Object Instances (Class Name) attribute_name=value ..... (Class Name) Class Class Name Class Name attribute attribute:datatype attribute = init_value ...... operation operation (arg_list) : return_type ...... Association Association Name Class-1 Class-2 role-1 role-2 Ternary Association Association Name Class-1 Class-2 role-1 role-2 role-3 Class-3

209 Object Model R eview Qualified Association: Class-1 qualifier Class-2Association Name Class-1 qualifier Class-2 role-1 role-2 Multiplicity of Associations Class Exactly one Class Many (zero or more) Class Optional(zero or one) 1+ Class One or more 1-2, 4 Class Numerically specified Ordering: {ordered} Class Link Attribute: Accessible by Class-1 User link attribute

210 Object Model R eview Generalization (Inheritance): SuperclassAggregation: Assembly Class Part-1-Class Part-2-Class Aggregation(alternate form): Assembly Class Part-1-Class Part-2-Class Generalization (Inheritance): Superclass Subclass-1 Subclass-2

211 Object Model Example: Object model of windowing system Windowdisplay undisplay raise lower Scrolling window x-offset y-offset scroll Canvas cx1 cy1 cx2 cy2 add-element delete-element Panel item name Event action notify event keyboard event Panel item x y label window elements Shape color line width Text Window string insert delete Scrolling canvas Line x1 y1 x2 y2 draw Closed shape fill color fill pattern Button string depressed Text item max lengrh current string Choice item {subset} Polygon Ellipse x y a b draw current choice choices draw Choice entry string value vertices {ordered} Point x y

212 Dynamic Model A state is an abstraction of the attribute values and links of an object. Sets of values are grouped together into a state according to propertities that affect the gross behaviow of the object. A state corresponds to the interval between two events received by an objects. Events represent points in time; states represent interval of time. Event causes Transition between States: event State-1 State-2 Initial and Final States: Initial State Intermediate State result

213 Dynamic Model An event is something that happens at a point in time, it conveys information from one object to another. Every event is a unique occurrence, but we group them into event classes and give each event class a name to indicate common structure and behavior. Event with Attribute: event(attribute) State-1 State-2 airplane flight departs (airline, flight, number, city) mouse button pushed (button, location) input string entered (text) phone receiver lifted digit dialed (digit) engine speed enters danger zone

214 Dynamic Model A scenario is a sequence of events that occurs during one particular execution of a system. caller lifts receiver dial tone begins caller dials digit(5) dial tone ends caller dials digit(1) caller dials digit(2) caller dials digit(3) caller dials digit(4) called phone begins ringing ringing tone appears in calling phone called party answers called phone stops ringing ringing tone disappears in calling phone phones are connected called party hangs up phones are disconnected caller hangs up

215 Dynamic Model A state diagram relates events and states. It is a graph whose nodes are states and whose directed arcs are transition label by event name. on-hook on-hook Idle off-hook time-out Dial tone Time-out digit(n) time-out digit(n) Dialing Recorded message invalid number valid number Busy tone number busy Connecting Fast busy tone message done trunk busy routed Ringing called phone answers Connected called phone hangs up Disconnected

216 Dynamic Model A condition is a Boolean function of object values. Conditions can be used as guards on transitions. A guarded transition fires when its event occurs, but only if the guard condition is true. Guarded Transition: event [guard] State-1 State-2

217 Dynamic Model An activity is an operation that takes time to complete. It is associated with a state. An action is an instantaneous operation. It is associated with an event. event (attribs)[condition1]/action1 State1 do:activity 1 State2 ... Actions for pop-up menu right button down / display popup menu Menu visible Idle right button up / erase popup menu cursor moved / highlight menu item

218 Dynamic Model State Diagram for phone line.on-hook on-hook Idle off-hook time-out on-hook Dial tone Time-out do:sound loud beep do:sound dial tone digit(n) time-out digit(n) Dialing Recorded message do: play invalid number on-hook Busy tone do:slow busy tone valid number number busy Connecting do:find connection on-hook Fast busy tone do:fast busy tone message done trunk busy routed on-hook Ringing do: ring bell called phone answers /connect line on-hook /disconnect line Connected called phone hangs up /connect line on-hook Disconnected

219 Dynamic Model The ways of structuring state machines are similar to the way of structuring objects: generalization and aggregation. Generalization is equivalent to expanding nested activities. Aggregation is equivalent to concurrenct of states.

220 Dynamic Model Nesting State Diagram:An activity in a state can be expanded as a low-level state diagram, each state representing one step of the activity. Vending machine model coins in(amount) / set balance Collecting money coins in(amount) / add to balance Idle cancel / refund coins [item empty] select (item) [change<0] do: test item and compute change [change=0] [change>0] do: dispense item do: make change Dispense item activity vending machine arm ready arm ready pushed do:move arm to correct row do:move arm to correct column do:push item off shelf Select item transition of vending machine digit(n) select(item) digit(n) do:reset item do: append digit enter clear

221 Dynamic Model State Generalization:State may have substates that inherit the transitions of their superstates, just as classes have subclasses that inherit the attributes and operations of their superclasses. Any transition or action that applies to a state applies to all its substates, unless overridden by an equivalent. State Generalization (Nesting): Superstate event1 Substate-1 Substate-2 event3 event2 State diagram of car transmission with generalization Transmission Push R Neutral Reverse Push N push N push F Forward stop upshift upshift First Second Third downshift downshift

222 Dynamic Model Event Generalization:Events can be organized into a generalization hierarchy with inheritance of event attributes. event time user input device mouse button location keyboard character mouse button down mouse button up control graphic space alphanumeric punctuation

223 Dynamic Model Aggregation Concurrency:A state diagram for an assembly is a collection of state diagrams, one for each component. Aggregation implies concurrency. An aggregation and its concurrent state diagrams Car Ignition Transmission Brake Accelerator Ignition turn key to start [Transmission in Neutral ] release key Off Starting On turn key off Transmission Push R Neutral Reverse Push N push F push N Forward stop upshift upshift First Second Third downshift downshift Accelerator Brake depress accelerator depress brake Off On Off On release accelerator release brake

224 Dynamic Model Concurrency within an object:Concurrency within the state of a single object arises when the object can be partitioned into subsets of attributes or links, each of which has its own subdiagram. Concurrent Subdiagrams: Superstate event1 Substate-1 Substate-3 Substate-2 Substate-4 event2 Playing rubber N-S vulnerability Not vulnerability N-S game N-S game N-S wins rubber vulnerability E-W vulnerability Not vulnerability E-W game E-W game N-S wins rubber vulnerability

225 Dynamic Model Entry and Exit Actions:Actions can be associated with entering or exiting a state. Internal Actions: An event can cause an action to be performed without a state change. When such an event occurs, its action is executed but not the entry or exit actions for the state. State1 do: activity1 entry / action2 exit / action3 event / action4 State2 event1 (attribs1) [condition1] / action1 event2 (attribs2) Object class

226 Dynamic Model If mutliple operations are specified on a state, they are performed in the following order: (1) action on the income transition. (2) entry action. (3) do activities. (4) exit actions. (5) actions on the outgoing transition.

227 Dynamic Model Automatic Transition:An arrow without an event name indicates an automatic transition that fires when the activity associated with the source state is completed. Sending Events: An object can perform the action of sending an event to another object. A system of objects interacts by exchanging events. Sending an event to another object: event1 State-1 State-2 event2 Class-3

228 Dynamic Model Synchronization of concurrent activities:Sometimes one object must perform two (or more) activities concurrently. Splitting of control: Synchronization of control: Substate-1 event1 Substate-3 event3 event0 Substate-2 event2 Substate-4 event4 Sychronization of control Emitting do: dispense cash cash taken Setting up ready Ready to reset do: eject card card taken

229 Dynamic Model Review: Event causes Transition between States:Initial and Final States: Initial State Intermediate State result Guarded Transition: event [guard] State-1 State-2 Actions and Activity while in a State State Name entry / entry-action do : activity-A event-1 / action-1 .... exit / exit-action Event with Attribute: event(attribute) State-1 State-2

230 Dynamic Model Review: Action on a Transition: event / action State-1Splitting of control: Synchronization of control: Substate-1 event1 Substate-3 event3 event0 Substate-2 event2 Substate-4 event4 State Generalization (Nesting): Superstate event1 Substate-1 Substate-2 event3 event2 Concurrent Subdiagrams: Superstate event1 Substate-1 Substate-3 Substate-2 Substate-4 event2

231 Dynamic Model Review: Output Event on a Transition:event1 / event2 State-1 State-2 Sending an event to another object: event1 State-1 State-2 event2 Class-3

232 Function Model The function model specifies what happens.The dynamic model specifies when it happens. The object model specifies what it happens to. The functional model shows a computation and the functional derivation of the data values init without indicating how, when or why the value are computed. The dynamic model control which operations are performed and the order in which they are applied. The object model defines the structure of values that operations operate on.

233 Function Model A data flow diagram (DFD) shows the functional relationships of the values computed by a system, including input value, output value and internal data. A DFD contains processes that transform data, data flow that move data, actor objects that produce and consume data, and data store objects that store data passively.

234 Function Model A process transforms data values.name dividend quotient integer division remainder divisor icon name pixel operations display icon location

235 Function Model A data flow connects the output of an object or process to the input of another object or process. Data Flow between Processes: data name process-1 process-2 Data flows to copy a value and split an aggregate value number street address city address state Zip code

236 Function Model An actor is an active object that derives the data flow graph by producing or consuming values. Actor Objects ( as Source or Sink of Data ): d1 d2 Actor-1 process Actor-1

237 Function Model A data store is a passive object within a DFD that stores data for later access. Data store or File Object: Name of data store Access of Data Store Value: Data Store d1 process Data Flow That Results in a Data Store: Name of data store Update of Data Store Value: Data Store d1 process Access and Updateof Data Store Value: Data Store d1 process

238 Readings max temp temperature min temp (a) Account balance withdrawalCustomer (b) item name Price list cost item name find coast cost (c)

239 Function Model Example: DFD for windowed graph display.Icon definitions size location application vector list window vector list icon name clip vectors offset vectors expand into vectors location screen vector list Screen buffer convert to pixels pixel operations

240 Function Model Nested Data Flow Diagram:A DFD is particularly useful for showing the high-level functionality of a system and its breakdown ito smaller functional units. icon name display icon pixel operations location Window Icon definitions size location application vector list window vector list icon name clip vectors offset vectors expand into vectors location screen vector list Screen buffer convert to pixels pixel operations

241 Function Model A control flow is a Boolean value that affects whether a process is evaluated. Control Flow: boolean result process-1 process-2 coded password Account verify password OK balance password amount update Customer cash

242 Function Model Specifying Operations:Process in DFD must eventually be implemented as operations on objects. Each bottom-level, atomic process is an operation. Specification of an operation includes a signature and transformation. The signature defines the interface to the operation: the argument it requires (number, order and type) the value it returns (number, order and type) The transformation defines the effect of an operation: the output values as functions of the input values the side effects of the operation on its operand objects.

243 Function Model The purpose of the specification is to indicate when an operation must do logically, not how it must be implemented. Therefore the state of the object itself must be divided into externally visible information and private internal information.

244 Function Model Review:Process: process name Data store or File Object: Name of data store Actor Objects ( as Source or Sink of Data ): d1 d2 Actor-1 process Actor-1 Access of Data Store Value: Data Store d1 process Update of Data Store Value: Data Store d1 process

245 Function Model Review:Data Flow between Processes: data name process-1 process-2 Data Flow That Results in a Data Store: Name of data store Control Flow: boolean result process-1 process-2 Decomposition of Data Value: composite d1 d2 Duplication of Data Value: d1 Access and Updateof Data Store Value: Data Store d1 process Composition of Data Value: d1 composite d2

246 Overview of analysis processUsers Developers Generate Requests Managers Problem Statement Analysis User interviews Build Models Domain Knowledge Object Model Dynamic Model Functional Model Real-word experience Design

247 Analysis Example: Automated Teller Machine (AT M) Cashier StationAccount ATM Bank Computer Account Central Computer ATM Account Bank Computer ATM Account

248 ATM Problem Statement:Design the software to support a computerized banking network including both human cashiers and automatic teller machines (AMT s) to be shared by a consortium of banks. Each bank provides its own computer to maintain its own accounts and process transactions agains t them. Cashier stations are owned by individual banks and communicate directly with their own bank'computers. Human cashiers enter account and transaction data. Automatic teller machines communicate with a central computer which clears transaction with the appropriate banks. An automatic teller machine accepts a cash card, interacts with the user, communicates with the central system to carry out the transaction, dispenses cash, and prints receipts. The system requires appropriate recordkeeping and security provisions. The system must handle concurrent accesses to the same account correctly. The banks will provide their own software for their own computers; you are to design the software for the ATMs and the network. The cost of the shared system will be apportioned to the banks according to the number of customers with cash cards.

249 Analysis -- Object ModelingThe steps that performed in constructing an object model: (1) Identify objects and classes (2) Prepare a data dictionary (3) Identity associations (Including aggregations) between objects. (4) Identify attributes of objects and links (5) Organize and simplify object classes using inheritance (6) Verify that access paths exist for likely queries (7) Iterate and refine the model (8) Group classes into modules

250 ATM Object Model Identifying object classes:Classes often correspond to nouns. Requirements Statement Tentative eliminate spurious classes Object extract nouns classes Object Classes ATM classes extracted from problem statement nouns Banking netware Software Cashier ATM Consortium Bank Bank computer Transaction Cashier statement Account data Transaction data Account Central computer Cash Card Cash Receipt System User Recordkeeping povision Security provision Access Cost Customer ATM classes idetified from knowledge of problem domain Communications line Transaction

251 ATM -- Object Model Keeping the R ight Classes:Bad Classes attribute irrelevant vague Account Data Receipt Cost System Cash Security Provision Transaction Data Recordkeeping Provision implementation Banking Network Transaction Log Access Software redundant Communications Line User Good Classes Account ATM Bank Bank Computer Cash Card Cashier Cashier Station Central Computer Consortium Customer Transaction

252 ATM -- Object Model Preparing a Data Dictionary:Account--a single account in a bank against which transactions can be applied. Ac- counts may be of various types, at least checking or savings. A customer can hold more than one account. ATM--a staion that allows customers to enter their own transactions using cash cards as identification. The ATM interacts with the customer to gather transaction in- formations, sands the transaction information to the central computer for validation operate independently of the network. Bank--a financial institution that holds accounts for customers and that issues cash cards authorizing access to accounts over the ATM network. Bank computer--the computer owned by a bank that interfaces with the ATM network and the bank's own cashier stations. A bank may actually have its own internal net- work of computers to process accounts, but we are only concerned with the one that talks to the network. Cash card--a card assigned to a bank customer that authorizes access of accounts using an ATM machine. Each card contains a bank code and a card number, most likely coded in accordance with national standards on credit cards and cash cards. The bank code uniquely identifies the bank within the consortium. The card number determines the accounts that the card can access. A card does not necessarilly ac- cess all of a customer's accounts. Each cash card is owned by a single customer, but mutiple copies of it may exist, so the possibility of simultaneous use of the same card from different machines must be considered. Cashier--an employee of a bank who is authorized enter transactions cashier stations and accept and dispense cash and checks to customers. Transactions, cash, and checks handled by each cashier must be logged and properly accounted for. Cashier station--a station on which cashiers enter transactions for customers. Cash- iers dispense and accept cash and checks; the station prints receipts. The cashier station communicates with the bank computer to validate and process the transac- tions. Central computer--a computer operated by the consortium which dispatches trans- actions between the ATMs and the bank computers. The central computer validates bank codes but does not process transactions directly. Customer--the holder of one or more accounts in a bank. A customer can consist of one or more persons or corporations; the correspondence is not relevant to this prob- lem. The same person holding an account at a different bank is considered a different customer. Transaction--a single integral request for operations on the accounts of a single cus- tomer. We only specified that ATMs must dispense cash, but we should not preclude the possibility of printing checks or accepting cash or checks. We may also want to provide the flexibility to operate on accounts of different customers, although it is not required yet. The different operations must balance properly.

253 Identifying Associations : ATM -- Object Model Identifying Associations : Any dependency between two or more classes is an association. Banking network includes cashiers and ATMs Consortium shares ATMs Bank provides bank computer Bank computer maintains acounts Bank computer processes transaction account Bank owns cahier station Cashier station communicates with bank computer Cashier enters transcation for account ATMs communicate with central computer about transaction Central computer clears transaction with bank ATM accepts cash card ATM interacts with user ATM dispenses cash ATM prints receipts System handles concurrent access Banks provide software Cost apportioned to banks Implicit verb phrases: Consortium consists of banks Bank holds account Consortium owns central computer System provides recordkeeping System provides security Customers haves cash cards Knowledge of problem domain: Cash card accesses accounts Bank employs cashiers

254 ATM Object Model Keeping the Right Associations: Consists of Holds HasConsortium bank code Bank Account Customer Concerns Employs Accesses Concerns Owns Owns Owns Communicates with Central computer Bank computer Cashier Has Enter by Communicates with Communicates with Cashier station Entered on Cashier transaction Entered on Remote transaction Cash card ATM Authorized by

255 Identifying Attributes:ATM -- Objcet Model Identifying Attributes: Attributes are properties of individual objects, it usually correspond to nouns followed by possessive phrases. issues card code Consists of account code Holds Has Account Consortium bank code Bank Customer employee code name balance credit limit type nmae address station code Employs Owns Owns Concerns Owns Central computer bank code Bank computer Cashier Communicates with name Accesses station code station code Has Concerns Enter by Communicates with Communicates with Cashier station Cashier transaction Entered on kind date-time amount Entered on Remote transaction Cash card ATM Authorized by cash on hand dispensed kind date-time amount password

256 ATM Object Model Refining with Inheritance:Inheritance can be added in two directions: by generalizing common aspects of existing classes into a superclass (bottom up) or by refining existing classes into specialized superclasses (top down). Transaction Entered on kind date-time amount Entry station concerns Cashier station ATM Cashier transaction Remote transaction cash on hand dispensed Communicates with Communicates with Entered by station code station code Authorized by Cashier Central computer Bank computer name bank code Employs Issues Communicates with Cash card Owns Owns Owns password Customer station code name address employee code Consortium Bank Has bank code bank code Accesses account code Account Consists of balance credit limit type Holds

257 Analysis -- Object ModelTesting Access Paths: Trace access paths through the object model diagram to see if they yield sensible result. Iterating Object Modeling: If a deficiency is found, go back to an earlier stage if necessary to correct it. Grouping Classes into Modules: A module is a set of classes that captures some logical subset of the entire model.

258 ATM -- Objcet Modeling ATM object model after revision: (??? Page number or position have to check)

259 Analysis -- Dynamic ModelingThe following steps are performed in constructing a dynamic model: (1) Prepare scenarios of typical interaction sequences. (2) Identify events between objects. (3) Prepare an event trace for each scenario. (4) Build a state diagram. (5) Match events between objects to verify consistency.

260 ATM -- Dynamic Model State diagram for class ATM: network respondsWait for network response Interrupt do:canceled message cancel insert card [readable] enter password Main screen do: display main screen do: result password do:verify account bad password insert card [readable] account OK take card Unreadable do:unreadable card message bad account cancel do:request kind cancel enter kind Card ejected do: eject card; request take card Cancel do:canceled message cancel do:request amount Finish do:print receipt do:bad account message terminate cancel enter amount continue transaction succeed take cash do:request continuation do:dispense cash; request take cash do:process transaction wait 5 seconds network responds = account OK, bad account bad bank code, bad password transaction failed transaction succeed transaction failed do:failure message cancel

261 ATM -- Dynamic Model State diagram for class Consortium:process transaction verify account [bad code] / bad bank code do:process bank transaction do:verify bank code [good code] bad bank account / bad account bank transaction failed / transaction failed do:verify card with bank bad bank password / bad password bank transaction succeed / transaction succeed bank account OK / account OK

262 S tate Diagram for class Bank:ATM -- Dynamic Model S tate Diagram for class Bank: verify card with bank process bank transaction [invalid] / bad bank account do:update account do:verify card number [valid] [invalid] / bad bank password [failure] bank transaction failed do:verify password [success] / bank transaction succeed [valid] / bank account OK

263 ATM -- Dynamic Model ATM object model after further revision:Transaction Consist of Entered on date-time Update account kind Entry station Cashier transaction Remote transaction Concerns Entered by Started by Cashier station ATM Cashier cash on hand dispensed name Issues Card authorization Employs Has Customer password limit Owns name address Owns station code ststion code Consists of employee code Identifies Consortium Bank Has bank code name card code Cash Card account code bank-code card-code serial number Account Holds balance credit limit type Accesses

264 Analysis -- Function ModelThe following steps are performed in constructing a functional model: (1) Identify input and output values. (2) Build data flow diagrams showing functional dependencies. (3) Describe functions. (4) Identify constraints. (5) Specify optimization crieria.

265 ATM -- Functional ModelIdentifying Input and Output Values: Input and output values for ATM system: Cash card bank code , card code password, transaction kind, account type, amount ATM system boundary cash, receipt, messages User

266 ATM -- Functional ModelBuilding Data Flow Diagrams: Top level data flow diagram for ATM: Account Cash card balance bank code, card code perform transaction read inputs generate outputs password, transaction kind, amount, account type messages, cash, receipt User

267 Data flow diagram for AT M perform transaction process.ATM -- Function Model Data flow diagram for AT M perform transaction process. Consortium bank code bad bank code select bank bank invalid card code card code select card card authorization password accounts password verify password bad password account type bad account select account Account balance transaction failed amount, transaction kind update account cash, receipt

268 ATM -- Function Model Describing functions:Function description for update account function: update account(account,amount,transaction-kind)->cash, receipt, message If the amount on a withdrawal exceeds the current account balance, reject the transaction and dispense no cash If the amount on a withdrawal does not exeed the current debit the account and dispense the amount requested If the transaction is a deposit credit the account and dispense no cash If the transaction is a status request depense no cash In any case, the receipt shows ATM number,date,time,account, number,transaction-kind,amount transacted(if any), and new balance

269 ATM -- Functional ModelIdentify constraints: No account balance may ever be negative. or No begative account balance may excess the credit limit for the account. Specifying Optimization Criteria: Minimize the time an account is locked for concurrency reasons.