
\documentclass[11pt]{article}
%\usepackage{mydraft}

\usepackage{TRmydraft}
\usepackage{wmff}
\usepackage{graphicx}
%\usepackage{graphalgb}

\pagestyle{myheadings}
\markright{}

\begin{document}

\reptitle{{\bf Object Oriented Programming}}
\author{Jos\'e M. Garrido}

\date{December, 2016}

\subtitle{{\bf Using OOSimL}}
\subsubtitle{An Overview - Part 3}
%\subsubtitle{Technical Report TR-CSIS-OOPsimL (Part 2)}

\authoraffil{Department of Computer Science} 
 
%
%\halftitlepage
%
\titlepage

\mdraft
%\maketitle
%\newpage
%\tableofcontents
%\newpage




%\include{ch08} % arrays

\section{Introduction to Arrays}

An array\index{array} is a static data structure that can store multiple values of the same type. These values are stored using contiguous memory locations with the same name. The values in the array are known as {\em elements}\index{elements}. Arrays can be used to store and manipulate a large number of values of the same type. This mechanism provides the ability to handle large number of values in a single collection and to refer to each value with an index. 

An integer value or variable known as {\em index\/}\index{index} is used to access a particular element of the array. The values of the index start from zero and it represents the relative position of the element in the array. Figure~\ref{fig:marray} shows an array with 10 elements.

\vspace{0.1in}
\begin{figure}[h]
\centereps{2.45in}{3.25in}{figs/marray.png}
\caption{An array with 10 elements}
\label{fig:marray}
%\vskip\baselineskip
\end{figure}
\vspace{0.1in}


An array is a static data structure because once the array is declared (and created), its size or capacity cannot change. An array is declared to hold 50 elements cannot be changed to hold a larger number of elements. The programmer will normally carry out  the following sequence of steps to use an array:

\begin{enumerate}
  \item Declaring the array with appropriate name and type
  \item Optionally assigning initial values to the array elements
  \item Manipulating the individual elements of the array
\end{enumerate}

%\vfill

\section{Array Declaration}

To declare an array, an identifier is used for the name of the array. The type of the array is a simple (primitive) type or a class. The general statement for declaring an array of a simple type is:

\vspace{0.1in}
%\begin{quote}
{\tt %\small
\begin{algorithm}
{\bf define} $\langle${\em array\_name} $\rangle${\bf array} [ ] {\bf of type} $\langle${\em array\_type} $\rangle$
\end{algorithm}
%\end{quote}
}
\vspace{0.1in}

Arrays of simple types\index{simple arrays} must be declared in the {\em variables\/} section of data definitions. In the following example an array {\em width\/} of type {\em float\/} is declared.

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
  variables
      define width array [] of type float
      . . .
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}


The statement for declaring an array of object references\index{array of references} has the general form:

\vspace{0.1in}
%\begin{quote}
{\tt %\small
\begin{algorithm}
{\bf define} $\langle${\em array\_name} $\rangle${\bf array} [ ] {\bf of class} $\langle${\em class\_name} $\rangle$  
\end{algorithm}
%\end{quote}
}
\vspace{0.1in}

Arrays of these types are declared in the {\em object references\/} section of data declarations. The following example declares an array {\em points\/} of class {\em Point}. 

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
  object references
      define points array [] of class Point
      . . .
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}

\section{Creating Arrays}

After an array has been declared, it must be created with an appropriate capacity or size, and then values can be assigned to specific elements. The capacity of the array is the number of elements it can hold. The general form of the statement for creating an array\index{creating arrays} is:

\vspace{0.1in}
%\begin{quote}
{\tt %\small
\begin{algorithm}
{\bf create} $\langle${\em array\_name} $\rangle${\bf array} [$\langle${\em capacity} $\rangle$] 
      \ \ \ \ \ \ {\bf of type} $\langle${\em array\_type} $\rangle$
\end{algorithm}
%\end{quote}
}
\vspace{0.1in}

The following statement creates array, {\em width}, with capacity of 50 elements. This array was already declared.
\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
      create temp array [50] of type float
      . . .
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}
  
The general form of the statement to create an array of object references is:

\vspace{0.1in}
%\begin{quote}
{\tt %\small
\begin{algorithm}
{\bf create} $\langle${\em array\_name} $\rangle${\bf array} [$\langle${\em capacity} $\rangle$] 
\ \ \ \ {\bf of class} $\langle${\em class\_name} $\rangle$  
\end{algorithm}
%\end{quote}
}
\vspace{0.1in}

An identifier constant is normally used to specify the capacity of the array. For example, given the constant {\em MAX\_NUM\/} has a value 50 and {\em NUM\_OBJECTS\/} a value of 25, the statements for declaring and creating the array {\em width\/} and array {\em points\/} are:

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
 constants
    define MAX_NUM = 50 of type integer
    define NUM_OBJECTS = 25 of type integer
 variables
    define width array [] of type float
 object references
    define points array [] of class Point
    . . .
 begin
    . . . 
    create width array [MAX_NUM] of type float
    create points array [NUM_OBJETS] of class Point
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}


The actual number of elements in the array is usually less than the total number or capacity of the array. For example, an array is declared with a capacity of 50 elements but only the first 20 elements of the array are used. An array is a static data structure, therefore elements cannot be inserted or deleted from the array. 


\section{Manipulating an Array}

Manipulating an array involve accessing the individual elements of the array and performing some computing. To access an individual element of an array, an integer value, known as the {\em index}, is used with the name of the array. The range of index values is 0 to the capacity of the array minus 1. 

%\subsection{Arrays of Simple Types}

To access a particular element of an array a statement uses the name of the array followed by the index value in rectangular brackets. The following {\bf set} statement assigns a value of 33.55 to element 3 of array {\em width\/}.

\vspace{0.1in}
%\begin{quote}
{\tt %\footnotesize
\begin{verbatim}
   set width[2] = 33.55   
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}

The index value used is an integer constant, a constant identifier, or an integer variable. The following statement uses a reference to element 3 of array {\em width\/} with variable {\em j\/} as the index.

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
   constants
      define MAX_NUM = 50 of type integer
   variables
      define width array [] of type float
      define j of type integer
      . . .
      create width array [MAX_NUM] of type float
      set j = 2
      set temp[j] = 33.55   
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}


%\subsection{Arrays of Object References}

An array of object references is not an array of objects since the objects are stored elsewhere in memory. The following statement creates an object of class Point and assigns this to element with index {\em j\/} of array {\em points\/} (of class Point):

\vspace{0.1in}
%\begin{quote}
{\tt %\footnotesize
\begin{verbatim}
   create points[j] of class Point   
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}

Element {\em j\/} of array {\em points\/} now refers to the newly created  object of class Point. To invoke a public function of an object referenced in an element of an array, the call statement is used followed by the name of the array and the index value enclosed in brackets. 

The following statement is used to invoke function {\em get\_xcoord\/} of the object referenced by element with index {\em j\/} of array {\em points}.


\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
variables
   define x of type float
   define j of type integer
   . . .
begin
   . . .
   set x = call get_xcoord of points[j]
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}

%\vspace{0.4in}

\section{Array Parameters}

An array may be defined as a parameter in the header of a function definition. When invoking this function, an array of the same or similar type can then be passed as argument. A reference to the array is passed in the function call. 

A function with an array parameter declares the array in the header of the function definition after the {\bf parameters}\index{parameters} keyword. The general form of a function header with a parameter definition is:

\vspace{0.1in}
%\begin{quote}
{\tt %\small
\begin{algorithm}
{\bf description}
\ \ . . .
\ */
{\bf function} $\langle${\em function\_name} $\rangle$
{\bf parameters} $\langle${\em parameter\_list} $\rangle${\bf is}
\ \ . . .
{\bf endfun} $\langle${\em function\_name} $\rangle$ 
\end{algorithm}
%\end{quote}
}
\vspace{0.1in}
 
The data declarations in {\em parameter\_list\/} section of the function header may have zero or more array declarations. The general form of these parameter declarations is:

\vspace{0.1in}
%\begin{quote}
{\tt %\small
\begin{algorithm}
$\langle${\em array\_name} $\rangle$ {\bf array} []
\ \ \ \ \ \ \ \ \ {\bf of type} $\langle${\em simple type or class} $\rangle$
\end{algorithm}
%\end{quote}
}
\vspace{0.1in}

The following example defines a function that finds the maximum value in an array of type {\em float\/}. The function defines the array parameter and an integer parameter. This second parameter is the number of elements in the array. The function returns the maximum value found. 

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
description
  This function calculates the maximum value of 
  an array parameter myarray, it then returns the
  result.
  */
function maximum return type float 
parameters myarray array [] of type float, 
           num of type integer is
variables
  define max of type float       // local variable
  define j of type integer
begin
  set max = myarray[0]
  for j = 1 to num - 1 do
      if max < myarray[j] then

         set max = myarray[j]
      endif
  endfor 
  return max 
endfun maximum 
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}

In the call to a function and passing an array as an argument, only the name of the array is used. The following code calls function {\em maximum\/} and pass array {\em marr\/} and constant {\em NUM\/} as arguments.

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
constants
   define NUM = 100 of type integer
variables
   define marr array [] of type float
   define maxval of type float
   . . .
   create marr array [NUM] of type float
   . . .
   set maxval = call maximum using marr, NUM
   . . .
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}

A function may also return the reference to an array. In the following example, a function creates an array {\em h\/} then returns a reference to this array.

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
   create h array [NUM] of type float
   . . .
   return h
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}



%\vfill
%\newpage

\section{Array Return Types}

The return type of a function can be specified to be of an array of a simple type or an array of a class. The following statement defines the general form of the return type in a class header.

\vspace{0.1in}
%\begin{quote}
{\tt %\small
\begin{algorithm}
{\bf function} $\langle${\em function\_name} $\rangle$
\ \ {\bf return} $\langle${\em type\_class} $\rangle${\bf array} [] $\langle${\em type\_class name} $\rangle$
\end{algorithm}
%\end{quote}
}
\vspace{0.1in}

In the following examples, two function definitions appear. The first example defines the return type of a function as an array of integer and  
the second example defines the return type of a function as an array of class Person.

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
  function arrayfun1 return type array [] integer
  parameters myarray array [] of class Person,
             num of type integer
  is
  . . . 
  endfun arrayfun1
  function arrayfun2 return class array [] Person
  parameters myarray array [] of class Point
  is
  . . .
  endfun arrayfun2
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}

  

\section{Arrays with Multiple Dimensions}

More than one dimension can be defined with arrays. Two-dimension arrays, also known as matrices\index{matrices}, are mathematical structures with values arranged in columns and rows. Two index values are required, one for the rows and one for the columns.

With two-dimensional arrays, two numbers are defined each in a pair of brackets. The first number defines the range of values for the first index (for rows) and the second number defines the range of values for the second index (for the columns).

The following statements declare and create a two-dimensional array named {\em tmatrix\/} with capacity 50 rows and 15 columns.

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
constants
   define ROWS = 50 of type integer
   define COLS = 15 of type integer
variables
   define tmatrix array [][] of type float
   . . .
   create tmatrix array [ROWS][COLS] of type float
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}

Two indexes are required to reference the elements of a two-dimensional array. The following statements assign all the elements of array {\em tmatrix\/} to 0.0:

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
   for j = 0 to COLS - 1 do
      for i = 0 to ROWS - 1 do
         set tmatrix [i][j] = 0.0
      endfor
   endfor 
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}

Two loop definitions are needed, an outer loop and an inner loop (this is also known nested loops). The inner loop varies the row index and outer loop varies the row index. The assignment statement sets the value 0.0 to the element at row $i$ and column $j$.


\section{Examples with Arrays}

In this section, several simple applications of arrays are discussed. These find the maximum, minimum, average values, others to carry out search and sorting in arrays.

\subsection{Finding Maximum and Minimum Values in an Array}

Finding the minimum and/or maximum values stored in an array, involve accessing all the elements of the array. The algorithm for finding the maximum value in pseudo-code is:

\begin{enumerate}
\item
 Assign the current largest value found  to be the value of the first element of the array.
\item
 Assign value zero to the index value of the first element.
\item
 Perform the following steps for each of the other elements of the array
\begin{enumerate}
  \item 
     Access the next element in the array.
  \item
     Examine its value, if the value of the current element is greater than the largest value so far, update the value found so far with this element value and save the index of the element.
\end{enumerate}
\item
The index value of the element value found to be the largest in the array is the result.
\end{enumerate}

The algorithm described is implemented in function {\em maxf\/}. The function uses array {\em myarr\/} of type {\em float\/} that has {\em num\/} elements. The function returns the index value with the largest value found.

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
 description
    This function of the element with the maximum 
    value in the array and returns its index.
    */
 function maxf return type integer
 parameters num of type integer,
            myarr array [] of type float
 is
    variables
       define j of type integer        // index variable
       // index of element with largest value
       define k of type integer            
       define max_val of type float    // largest value 
    begin
       set k = 0              // index first element
       set max_val = myarr[0] // max value so far
       for j = 1 to num - 1 do
          if myarr[j] > max_val
          then
             set k = j

             set max_val = myarr[j]
          endif
       endfor
    return k                 // result
 endfun maxf 
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}


\subsection{The Average Value in an Array}

To compute the average value in an array, all the elements have to be added to an accumulator variable, {\em sum}. The algorithm for computing the average value in pseudo-code is:

\begin{enumerate}
\item
 Assign the accumulator variable, {\em sum\/}, to the value of the first element of the array.
\item
 For each of the other elements of the array, add the value of the next element in the array to the accumulator variable.
\item
Divide the value of the accumulator variable by the number of elements in the array. This is the result value calculated.
\end{enumerate}

An accumulator variable is used to store the summation of the element values in the array. In an array $x$ with $n$ elements. The summation of $x$ with index $j$ starting with $j = 1$ to $j = n$ is expressed mathematically as:


  $$ sum = \sum_{j=1}^n x_j. $$

Function {\em averagef\/} implements the algorithm. The function uses array {\em myarr\/}, which is declared as an array of type {\em float\/} and has {\em num\/} elements. The function returns the average value calculated. 

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
 description
    This function calculates the average of the 
    elements in array myarr. 
    */
 function averagef return type float
 parameters myarr array of type float,
            num of type integer
 is
    variables
      define sum of type float    // variable for summation
      define avg of type float    // average value
      define j of type integer
   begin
      set sum = 0
      for j = 0 to num - 1 do
         add myarr[j] to sum
      endfor
      set avg = sum / num
      return avg
 endfun averagef
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}

\subsection{Searching}

Searching involves examining the elements of an array for an element with particular value. Not all the elements of the array need to be examined, the search ends when and if an element of the array has a value equal to the requested value. There are two general techniques for searching: linear search and binary search.

\subsubsection{Linear Search}

Linear search finds the element with a specified value. The algorithm starts to compare the requested value with the value in the first element of the array and if not found, compare with the next element and so on until the last element of the array is compared with the requested value. 

The result of this search is the index of the element in the array that is equal to the requested value. If the requested value is not found, the result is a negative value. The algorithm description in informal pseudo-code is:

\begin{enumerate}

\item
 Repeat for every element of the array:
  \begin{enumerate}
    \item
      Compare the current element with the requested value. If the values are equal, store the value of the index as the result and search no more.
    \item
      If values are not equal, continue search.
  \end{enumerate}
\item
 If the value requested is not found, set the result to value -1.
\end{enumerate}  


Function {\em searcht\/} searches the array for an element with the requested temperature value, {\em t\_val}. For the result, the function assigns to {\em t} the index value of the element with the value requested. If the requested value is not found, the function assigns a negative integer value to {\em t}. 


\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
  description
    This function carries out a linear search of
    the array of temperature for the temperature
    value in parameter t_val. It sets the index
    value of the element found, or -1 if not found.
    */
  function searcht return type integer
  parameters t_val of type float,
             myarr array [] of type float,
             num of type integer
  is
    variables
      define j of type integer
      define found = false of type boolean 
    begin
      set j = 0
      while j < num and found not equal true do
        if myarr [j] == t_val
        then
           set t = j
           set found = true
        else
           increment j
        endif
      endwhile
      if found not equal true
      then
         set t = -1
      endif
      return t
  endfun searcht
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}


\subsubsection{Binary Search}

 In this type of search technique, the values to be searched have to be sorted in some given ascending order. The part of the array elements to include in the search is split into two partitions of about the same size. The middle element is compared with the requested value. If the value is not found, the search is continues on only one partition. This partition is again split into two smaller partitions until the element is found or until no more splits are possible (not found). The binary search technique applied to a sorted array.

Binary search is a very efficient search technique compared to linear search because the number of comparisons is smaller. The efficiency of a search algorithm is determined by the number of relevant operations in proportion to the size of the array to search. The significant operations in this case are the comparisons of the element values with the requested value.

For an array with $N$ elements, the average number of comparisons with linear search is $N/2$, and if the requested value is not found, the number of comparisons is $N$. With binary search, the number of comparisons is $\log_2 N$. The description of the algorithm in pseudo-code is:

\newpage

\begin{enumerate}
\item
 Set up the lower and upper bounds of the array.
\item
Repeat the search while the lower index value is less than the upper index value.
\begin{enumerate}
\item
 Split the array into two partitions. Compare the middle element with the requested value.
\item
If the value of the middle element is the search value, the result is the index of this element, search no more.
\item
 If the search value is less than the middle element, change the upper bound to the index of the middle element minus 1. The search will continue on the lower partition.
\item
 If the search value is greater or equal to the middle element, change the lower bound to the index of the middle element plus 1. The search will continue on the upper partition.
\end{enumerate}
\item
  If the search value is not found, the result is -1.
\end{enumerate}

Function {\em bsearcht\/} implements the binary search algorithm using array parameter {\em myarr}. 

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
description
    This function implements a binary search of
    the myarr array using search value in 
    parameter t_val. It sets the index
    value of the element found, or -1 if not found.
    */
function bsearcht return type integer
parameters t_val of type float
           myarr array [] of type float
           num of type integer            
is
variables
      define t of type integer
      define found = false of type boolean 
      define lower of type integer // index lower bound
      define upper of type integer   // index upper bound
      define middle of type integer  // index of middle
begin
      set lower = 0
      set upper = num
      while lower < upper and found not equal true 
      do
        set middle = (lower + upper) / 2
        if t_val == myarr[middle] 
        then
           set found = true
           set t =  middle
        else
           if t_val < myarr[middle]
           then
              set upper = middle -1
           else
              set lower = middle + 1
           endif
        endif
      endwhile
      if found not equal true
      then
         set t = -1
      endif
      return t
endfun searcht
\end{verbatim}
}
%\end{quote}
\vspace{0.1in}


\subsection{Sorting}

Sorting is a technique that consists of rearranging the elements of the array in specified some order. If the values of the array to be sorted are numerical, then the two possible orders are ascending and descending. If the values of array are strings, then alphabetical order is the most practical. Some of the most widely known sorting algorithms are:

\begin{itemize}

\item
 Selection sort
\item
 Insertion sort
\item
 Bubble sort
\item
 Shell sort
\item
 Merge sort
\item Quick sort
\end{itemize}


Selection sort is a very simple sorting algorithm. Given an array of a numerical type of size $N$, the algorithm performs several steps. First, it finds the index value of the smallest element value in the array. Second, it swaps this element with the element with index 0 (the first element. This step actually places the smallest element to the first position. Third, the first step is repeated for the part of the array with index 1 to $N-1$, this excludes the element with index 0, which is at the proper position. The smallest element found is swapped with the element at position with index 1. This is repeated until all the elements are located in ascending order. The algorithm description in pseudo-code is:

\begin{enumerate}
\item
 Repeat the following steps for all elements with index J = 0 to N-2
\item
  Search for the smallest element from index J to N-1. 
 \item
  Swap the smallest element found with element with index J, if the smallest element is not the one with index J.
\end{enumerate}


The following function {\em selectionsort\/} implements the algorithm for the selection sort. 

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
  description
    This function implements a selection sort of
    the array.
    */
  function selectionsort 
  parameters myarr array [] of type float,
             num of type integer
  is
    variables
      define N of type integer     // elements in array
      define Jmin of type integer  // smallest element
      define j of type integer
      define k of type integer
      define t_val of type float   // intermediate value
\end{verbatim}
%\end{quote}
}

\newpage

{\tt \small
\begin{verbatim}            
      
    begin
      set N = num
      for j = 0 to N - 2 do
        // search for the smallest element
        // in the index range from j to N-1
        set Jmin = j
        for k = j+1 to N - 1 do
          if myarr[k] < myarr[Jmin]
          then
             set Jmin = k
          endif
        endfor
        if Jmin != j 
        then
           // swap elements with index J and Jmin
           set t_val = myarr[j]
           set myarr[j] = myarr[Jmin]
           set myarr[Jmin] = t_val
        endif
      endfor
  endfun selectionsort
\end{verbatim}
%\end{quote}
}
\vspace{0.1in}

The efficiency of the algorithm is formally expressed as $O(N^2)$. The number of element comparisons with an array size of $N$ is $N^2/2 - N/2$. The first term ($N^2/2$) in this expression is the dominant one; the order of growth of this algorithm is $N^2$. 

%\newpage

%\include{chap_inherit} % Inheritance

\section{Introduction to Inheritance}

Inheritance is a class relationship\index{class relationship} among classes. The other basic class relationship is composition, which is a stronger form of association\index{association}. These relationships are easily modeled in UML diagrams. Composition is a horizontal relationship and inheritance is a vertical relationship.

Inheritance\index{inheritance} is a facility provided by an object-oriented language for defining new classes from existing classes. The basic inheritance relationships and their applications are explained in some detail. Inheritance enhances class reuse, that is, the use of a class in more than one application. 

\section{Modeling Classes}

A class is defined as a group of objects with common characteristics. Some classes of an application are completely independent because they do not have any relationship with other classes. The other classes in an application are related in some manner and they form a hierarchy of classes, therefore, class relationships must also be identified.

To help describe a class hierarchy\index{class hierarchy}, the most general class is placed at the top. This is known as the  {\em parent} class and is also known as the {\em super\/} class (or the {\em base\/} class). A {\em subclass\/}\index{subclass} inherits the \index{characteristics} (all attributes and operations) of its parent class. These characteristics of a class are also known as features.

A subclass can be further inherited to lower-level classes. In the UML class diagram, an arrow with an empty head points from a subclass (the derived class) to its base class to show that it is inheriting the features of its base class. 

From UML diagram description of this type of class relationship, inheritance\index{inheritance} is seen as a vertical relationship between two classes.  Figure~\ref{fig:tinheritance} illustrates this class relationship. Class {\em Motor Vehicle\/} is the base class, the other three classes inherit the features of this base class. 

\vspace{.1in}
\begin{figure}[h]
\centereps{3.5in}{1.65in}{figs/inheritance.eps}
\caption{Class inheritance}
\label{fig:tinheritance}
\end{figure}
\vspace{0.1in}

The terminology varies somewhat in different software environments. In UML, the term {\em generalization\/} is used instead of inheritance. In the Java programming language, the term {\em extends\/} is used for a class that inherits features from a base class. 

\section{Inheritance}

In defining a new class using inheritance, the newly defined class acquires all the non-private features of an existing parent class. This mechanism is provided by most object-oriented programming languages. The parent class is also known as the {\em base\/} class, or the {\em super\/} class. The new class being defined is known as a {\em derived\/}\index{derived} class or {\em subclass\/}\index{subclass}. 

The base class\index{base class} is a more general class than its subclasses. 
A derived class can be defined by adding more features or modifying some of the inherited features\index{inherited features}. Therefore, a subclass can be defined as:

\begin{itemize}
  \item
 An extension of the base class, if in addition to the inherited features, it includes its own attributes and operations.
  \item
 A specialized version of the base class, if it overrides (redefines) one or more of the features inherited from its parent class

  \item
A combination of an extension and a specialization of the base class 

\end{itemize}

Using UML, the term {\em generalization}\index{generalization} is defined as the association between a general\index{general class} class and a more specialized\index{specialized class} class or extended\index{extended class} class. This association is also known as {\em inheritance}\index{inheritance}, and it is an important relationship\index{class relationship} between two classes. In the UML class diagram, the arrow that represents this relationship points from a class (the derived class) to its parent class. 

The purpose of inheritance is to define a new class from an existing class and to shorten the time compared to the development of a class from scratch. Inheritance also enhances class reuse. 

The ability of a class to inherit the characteristics from more than one parent class is known as {\em multiple inheritance\/}. Most object-oriented programming languages support multiple inheritance. The OOSimL and Java languages only support single inheritance. 

A simple class hierarchy with inheritance is shown in   Figure~\ref{fig:tinheritance}. The base\index{base class} class is {\em Motorvehicle\/} and the subclasses are: {\em Car}, {\em Motorcycle}, and {\em  Truck\/}. 

All objects of class {\em Truck\/} in   Figure~\ref{fig:tinheritance} are also objects of class {\em Motorvehicle}, because this is the base class for the other classes. On the contrary, not all objects of class {\em Motorvehicle\/} are objects of class {\em Truck}. 

%\vfill

\subsection{Defining Subclasses with OOSimL}

As mentioned previously, the public\index{public} features of the base class are inherited by the subclass. Protected features are inherited by the subclass, but the access is limited to classes in the same package.

The definition of a subclass in OOSimL must include the keyword {\bf inherits} followed by the name of the base class. The general form of the OOSimL statement for the header in the definition of a subclass is:

\vspace{0.1in}
{\tt 
\begin{algorithm}
{\bf description}
\ \ \ \dots
{\bf class} $\langle${\em class\_name} $\rangle${\bf inherits} $\langle${\em base\_class\_name} $\rangle$ {\bf is}
\ \ {\bf private}
\ \ \ \ \dots
\ \ {\bf protected}
\ \ \ \ \dots
\ \ {\bf public} 
\ \ \ \ \dots
{\bf endclass} $\langle${\em class\_name} $\rangle$ 
\end{algorithm}
}
\vspace{0.1in}


In UML class diagrams, a feature of the class is indicated with a plus (+) sign if it is public, with a minus (-) sign if it is private, and with a pound (\#) sign if it is protected.

\subsection{Inheritance and Initializer Functions}

The initializer\index{initializer} functions of a base class are the only public features that are not inherited by the subclasses. An initializer function of a subclass should initialize its own attributes (variables and object references) as well as the attributes defined in the base class. Therefore, when defining an initializer\index{initializer} function of a subclass, it will normally invoke the initializer function of the base class. 

The special name given to the initializer function of the base class is {\em super}\index{super}. This call must be the first statement in the initializer function of the subclass. Calling function {\em super\/} may require arguments, and these must correspond to the parameters defined in the initializer function of the base class. 

The statement to call or invoke an initializer function of the base class from the subclass is:

\vspace{0.1in}
{\tt 
\begin{algorithm}
{\bf call super} $\langle${\bf using}{\em argument\_list} $\rangle$ 
\end{algorithm}
}
\vspace{0.1in}

If the argument list is absent in the call, the initializer function invoked is the default initializer of the base class. 

In the following example, a new class, {\em Student}, is defined that inherits the features of an existing (base) class {\em Person}. The attributes of class {\em Person\/} are {\em pnumber}, {\em age}, {\em name}, and {\em address}. The initializer function of class {\em Person} sets initial values to these attributes.

The subclass {\em Student} has two other attribute, {\em major\/} and {\em gpa}. The initializer function of this class invokes the initializer function of the base class and sets initial values to its two attributes, {\em major\/} and {\em gpa}. The following code shows this part of class {\em Student}.

\vspace{0.1in}
{\tt \small
\begin{verbatim}
class Student inherits Person is
  private
  variables                   
      define major of type integer
      define gpa of type float
  public    
  description
    This is the constructor, it initializes a Student 
    Object on creation.
    */
  function initializer 
  parameters 
             imajor of type integer,
             igpa of type float,
             iname of type string, 
             ipnum of type long, 
             iage of type integer,
             iaddress of type string
  is
  begin
    // invoke the initializer of the base class
    call super using iname, ipnum, iage, iaddress
    set major = imajor
    set gpa = igpa
  endfun initializer 
  . . .
  endclass Student
\end{verbatim}
}
\vspace{0.in}

The attributes of a class are usually private, so the only way to set the initial values for the attributes of the base class is to invoke its initializer function of the base class. 

In the previous code, this is accomplished with the statement:

\vspace{0.1in}
{\tt \small
\begin{verbatim}
  call super using iname, ipnum, iage, iaddress
\end{verbatim}
}
%\vspace{0.1in}

\subsection{Complete Example with Inheritance}


The following source code shows the implementation of the base class, {\em Person}. The attributes of class {\em Person\/} are {\em pnumber}, {\em age}, {\em name}, and {\em address}. The initializer function of class {\em Person} sets initial values to these attributes.


\vspace{0.1in}
{\tt \small
\begin{verbatim}
description
  This class represents person data. The attributes are
    ID number, age, address, and name.
  */
class Person is
  private
  variables                   
      define pnumber of type long
      define age of type integer
      define name of type string
      define address of type string
  public    
  description
    This is the constructor, it initializes a Person object 
    on creation.
    */
  function initializer 
  parameters iname of type string, 
             ipnum of type long, 
             iage of type integer,
             iaddress of type string
  is
  begin
    //
    set pnumber = ipnum
    set age = iage
    set name = iname
    set address = iaddress
  endfun initializer 
  //
  description
    This funtion gets the person mumber of the 
	 Person object.    */
  function get_pnum return type long is
  begin    
      return pnumber 
  endfun get_pnum 
  //
  description
    This function returns the name of the employee object.
    */
  function get_name return type string is
    begin
      return name 
  endfun get_name 
  //
  description
     This function returns the address increase for the object.
     */
  function get_address return type string is
  begin
     return address
  endfun get_address
  //
  description
     This function displays the attributes of the Person object
     */
  function display_data is
  begin
      display name, " ", age, " ", address
  endfun display_data
endclass Person 
\end{verbatim}
}
\vspace{0.1in}

%\newpage

The following code shows the implementation of class {\em Student}, which is a subclass of class {\em Person}. 

\vspace{0.1in}
{\tt \small
\begin{verbatim}
description
  This class represents student objects. The attributes are
    major and GPA. The major is coded to an integer number.
    This class inherits class Person.
  */
class Student inherits Person is
  private
  variables                   
      define major of type integer
      define gpa of type float
  public    
  description
    This is the constructor, it initializes a Student 
    on creation.
    */
  function initializer 
  parameters 
             imajor of type integer,
             igpa of type float,
             iname of type string, 
             ipnum of type long, 
             iage of type integer,
             iaddress of type string
  is
  begin
     // invoke the initializer of the base class
     call super using iname, ipnum, iage, iaddress
     set major = imajor
     set gpa = igpa
  endfun initializer 
  //
  description
    This funtion gets the student major of the 
	  object.    
  */
  function get_major return type integer is
  begin    
      return major 
  endfun get_major
  //
  description
    This funtion sets the student major of the 
	object.    */
  function set_major parameters pmajor of type integer is
  begin    
      set major = pmajor
  endfun set_major
  //
  description
    This function returns the GPA of the student object.
    */
  function get_gpa return type float is
  begin
      return gpa 
  endfun get_gpa 
  //
  description
    This function sets the GPA of the student object.
    */
  function set_gpa parameters pgpa of type float is
  begin
      set gpa = pgpa
  endfun set_gpa  
  //
  description
     This function displays the attributes of the 
     student object. it overrides the function of 
     the base class
     */
  function display_data is
  begin
      call super.display_data
      display major, " ", gpa
  endfun display_data
endclass Student
\end{verbatim}
}
\vspace{0.1in}

%\vspace{0.4in}



\subsection{Function Overriding}
 
A subclass is a {\em specialization\/}\index{specialization} of the base class if one or more functions of the base class are {\em redefined\/} (or overridden\index{method overriding}) in the subclass. The subclass is said to reimplement one or more functions of the base class.

In class {\em Student}, which was shown previously, function {\em display\_data\/} is a redefinition of the function with the same name in the base class. Class {\em Student\/} inherits class {\em Person\/} and overrides function {\em display\_data}. Therefore, class {\em Student} is an extension and also a specialized version of class {\em Person}. 


%\include{adv_oo} % Advanced OO concepts


\section{Abstract Classes}

An abstract class\index{abstract class} has  one or more {\em abstract functions\/}\index{abstract function}. An abstract function has only its declaration (also called its specification) and no implementation is included. A pure abstract class has all its functions declared as abstract.

Because an abstract class has one or more functions without their implementations, the class cannot be instantiated and it is generally used as a base class. The subclasses override the abstract functions inherited from the abstract base class and provide implementation for these functions. 

\subsection{Definition of Abstract Classes}

In OOSimL, the keyword {\bf abstract} is used before the keyword {\bf class} when defining an abstract class. The definitions of abstract functions are also preceded by the keyword {\bf abstract}. The OOSimL statements for abstract class definition has the following general form:

%\newpage

\vspace{0.1in}
{\tt
\begin{algorithm}
{\bf description}
\ \ \ . . .
{\bf abstract class} $\langle${\em class\_name} $\rangle$ {\bf is}
\ {\bf private}
\ \ \ \ . . .
\ {\bf protected} 
\ \ \ \ . . .
\ {\bf public} 
\ \ \ \ . . .
{\bf endclass} $\langle${\em class\_name} $\rangle$ 
\end{algorithm}
}
\vspace{0.1in}

As mentioned previously, an abstract class is normally defined as a base\index{base class} class. Base classes provide single  general descriptions for the common functionality and structure of its subclasses.  Therefore, an abstract class is a foundation on which to define subclasses. Classes that are not abstract classes are known as {\em concrete classes}\index{concrete class}. 

For example, a class that represents basic geometric figures is defined as an abstract class.  Two functions {\em area\/} and {\em perimeter\/} are declared in the class. These fucntions  compute the area and the perimeter of a figure. Class {\em Genfig\/} is defined   in the following code:

\vspace{0.1in}
{\tt \small 
\begin{verbatim}
description
   This is an abstract class that defines a generic
   geometric figure
   */
abstract class Genfig is
public
  // compute are of geometric figure
  abstract function area return type double
  // 
  // compute perimeter of geometric figure
  abstract function perimeter return type double
endclass Genfig
\end{verbatim}
}
\vspace{0.1in}

The base class {\em Genfig} is defined as an abstract class because it does not provide the implementation of the functions {\em area\/} and {\em perimeter}.

%\vspace{0.1in}
\begin{figure}[h]
\centereps{3.25in}{3.25in}{figs/gfigures.eps}
\caption{A class hierarchy of geometric figures}
\label{fig:gfigures}
%\vskip\baselineskip
\end{figure}
\vspace{0.1in}

Figure~\ref{fig:gfigures} shows the class hierarchy with base class {\em Genfig} and three subclasses: {\em Rectangle\/}, {\em Triangle\/}, and {\em Circle}. The calculations of area and perimeter are different in each of these subclasses and the base class {\em Genfig} cannot include the implementations for these functions. The base class only provides the declaration (prototypes) for these functions. 


Because the abstract class {\em Genfig} does not include the implementation body of the functions {\em area\/} and {\em perimeter\/}, objects of this class cannot be created. In other words, class {\em Genfig} cannot be instantiated.


\subsection{Inheriting Abstract Classes}

Because an abstract base class does not provide an implementation to one or more of its functions, the subclasses\index{subclass} that inherit an abstract base class have to override (redefine) the functions that are defined as abstract functions in the abstract base class. The subclass, {\em Triangle\/}, for example, inherits class {\em Genfig} and includes the specific implementation of the functions {\em area\/}, {\em perimeter\/}, and the relevant attributes. The following code implements class {\em Triangle}. 

\vspace{0.1in}
{\tt \small
\begin{verbatim}
description
      This class computes the area and perimeter 
      of a triangle, given its three sides.
      */
class Triangle inherits Genfig is
  private
  variables
      define x of type double   // first side 
      define y of type double   // second side
      define z of type double   // third side
  public
  description
      This function sets values for the three
      sides of the triangle.      */
  function initializer parameters a of type double, 
                  b of type double, c of type double is
  begin
      set x = a
      set y = b
      set z = c
endfun initializer
//
  description
    This function computes the perimeter of a 
    triangle. */
  function perimeter return type double is
  variables     
       define lperim of type double
  begin                          
       set lperim = x + y + z
       return lperim
endfun perimeter
//
  description
     This function computes the area of a 
     triangle.     */
  function area return type double is
  variables
       define s of type double    // intermediate result
       define r of type double
       define larea of type double
  begin
       set s = 0.5 * (x + y + z)
       set r = s * (s - x)*(s - y)*(s - z)
       set larea = call Math.sqrt using r
       return larea
  endfun area
endclass Triangle
\end{verbatim}
}
\vspace{0.1in}

\section{Interfaces}

An interface\index{interface} does not include constructors and cannot be instantiated. However, none of the functions of an interface  include implementation, does not include attribute definitions although constant definitions are allowed. An interface is similar to a pure abstract class.

\subsection{Interface Definition}

The keyword {\bf interface} is used followed by the name of the interface, in defining an interface\index{interface}. For the functions, the keyword {\bf abstract} is not needed because all the functions are abstract functions. All features of an interface are implicitly public. The  definition of an interface in OOSimL has the following general structure:

%\newpage

\vspace{0.1in}
{\tt
\begin{algorithm}
{\bf description}
\ \ \ . . .
{\bf interface} $\langle${\em interface\_name} $\rangle$ {\bf is}
\ {\bf public} 
\ {\bf constants}
\ \ \ \ . . .
\ // public functions
\ \ \ \ . . .
{\bf endinterface} $\langle${\em interface\_name} $\rangle$ 
\end{algorithm}
}
\vspace{0.1in}

An interface, {\em IGenfig}, is shown in the following code. It defines the specification for the behavior of objects of any class that implements this interface.  Note that the form of the interface is very similar to that of a pure abstract class. 

\vspace{0.1in}
{\tt \small
\begin{verbatim}
description
   This is an interface that defines a generic
   geometric figure
   */
interface IGenfig is
 public
  // compute are of geometric figure
  function area return type double 
  //
  // compute perimeter of geometric figure
  function perimeter return type double
endinterface IGenfig
\end{verbatim}
}
\vspace{0.1in}

\subsection{Implementing an Interface}

All methods declared in the interface must be implemented\index{implement} in the class that implements it. This class can define additional features. 
The header of the class that implements an interface has the keyword {\bf implements} followed by the name of the interface. The class header has the general form:

\vspace{0.1in}
{\tt 
\begin{algorithm}
{\bf description}
\ \ \ . . .
{\bf class} $\langle${\em cls\_name} $\rangle${\bf implements} $\langle${\em interface\_name} $\rangle$ {\bf is}
\ \ \ \ . . .
{\bf endclass} $\langle${\em cls\_name} $\rangle$ 
\end{algorithm}
}
\vspace{0.1in}


Two additional and important differences between an interface and an abstract class is that multiple interfaces can be implemented by a class, whereas only one abstract base class can be inherited by a subclass, and it is mandatory for a class that implements an interface to implement all the functions defined in the interface.
 
\section{Object Types}

Abstract classes and interfaces can be used as {\em super types\/}\index{super type} for object references. Although they cannot be instantiated, interfaces and abstract classes are useful for declaring object references\index{object reference}.

In the example of geometric figures, class {\em Genfig} is an abstract class  and the other classes are subclasses\index{subclass}. An object reference can be declared of type {\tt Genfig}. Objects of the subclasses can be declared of each of their classes. The subclasses are considered subtypes of type {\em Genfig}. The following lines of code declare four object references, {\em gfigure}, {\em triangle\_obj\/}, {\em circle\_obj\/}, and {\em rect\_obj}.


\vspace{0.1in}
{\tt \small
\begin{verbatim}
   define gfigure of class Genfig
   define triangle_obj of class Triangle
   define circle_obj of class Circle
   define rect_obj of class Rectangle
\end{verbatim}
}
\vspace{0.1in}
  

   
The types of these object references declared are considered subtypes\index{subtypes} in the problem domain because of the original class hierarchy represented in Figure~\ref{fig:gfigures}. 

The object reference {\em triangle\_obj\/} is declared of type {\em Triangle}, but is also of type {\em Genfig\/} and any object reference of type {\em Triangle\/} is also of type {\em Genfig}. 

The principle holds going upward in the class hierarchy, the opposite is not true; any object reference of type {\em Genfig\/} is not also of type {\em Rectangle}. 

An interface\index{interface} can also be used as a super type, and all the classes that implement the interface are subtypes.


\section{Polymorphism}

{\em Polymorphism\/}\index{polymorphism} is a runtime mechanism of an object-oriented language. This mechanism selects the appropriate version of a function to be executed depending on the actual type of the object. This function selection is based on {\em late binding} that occurs at execution time. 

The typing principle explained previously allows an object reference of a super type\index{supertype} to reference an object of a subtype. The following code creates objects for the object references {\em triangle\_obj\/}, {\em circle\_obj\/}, and {\em rect\_obj}. 

\vspace{0.1in}
{\tt \small 
\begin{verbatim}
 create triangle_obj of class Triangle using x, y, z
 create circle_obj of class Circle using r
 create rect_obj of class Rectangle using x, y 
\end{verbatim}
}
\vspace{0.1in}

An object reference {\em gfigure\/} of class {\em Genfig} can be assigned to refer to any of the object of a subtype. The following code implements such an assignment.

\vspace{0.1in}
{\tt \small
\begin{verbatim}
 set gfigure = triangle_obj
\end{verbatim}
}
\vspace{0.1in}

In this assignment, the type of object reference {\em triangle\_obj\/} is a subtype of the type of object {\em gfigure}. It is legal to invoke a function of the abstract class {\em Genfig} that is implemented differently in the subclasses. The following code invokes function {\em perimeter}:

\vspace{0.1in}
{\tt \small
\begin{verbatim}
 call perimeter of gfigure
\end{verbatim}
}
\vspace{0.1in}

The actual function invoked is the one implemented in class {\em Triangle}, because it is the actual type of the object reference {\em triangle\_obj}. Another similar assignment can be included at some other point in the program. 

The following code assigns the object reference {\em circle\_obj} to the object reference {\em gfigure} and the call to function {\em perimeter\/} is the same as before, because the three subtypes represented by the three subclasses {\em Rectangle}, {\em Circle}, and {\em Triangle} each implement function {\em perimeter}. 

\vspace{0.1in}
{\tt \small
\begin{verbatim}
 set gfigure = circle_obj
 call perimeter of gfigure
\end{verbatim}
}
\vspace{0.1in} 

Because the implementation for function {\em perimeter\/} is different in the three classes, the runtime language system  selects the right version of the function to call.



\end{document}


