Abstract data types¶

Examples on abstract data types¶

For example, the type int can be considered as an abstract data type. A programmer can use it by means of the usual arithmetic operations (+, -, *, /) without caring of how the type int has been implemented. (Possible ways to implement it would be one’s complement, two’s complement, and BCD (binary coded decimal), but such things are not relevant on this course.)

Provided operations must be reasonable for the type. For example, the possible values of a traffic light type could be red, yellow, and green. The type could be implemented as an enumerated type (enum), when the aforementioned values correspond to integers 0, 1, and 2. However, addition between different colors would not be a reasonable operation for the type, but changing the color from one to another would be such.

In earlier assignments, we have implemented a card deck resembling a stack. A stack can be considered as an abstract data type, the values of which are the elements of the stack and the operations of which are push (inserting an element as the top element of the stack) and pop (removing the top-most element). In practice, we will also need operations for creating an empty stack and for checking if the stack is empty.

The aforementioned card deck was implemented as a linked list, but the user need not care about the implementation. Another choice would be to implement a stack as an array or as a vector, but anyway the public interface of the operations push ja pop would remain the same.

Information hiding and encapsulation¶

Abstract data types are closely related to modularity, since abstract data types can be implemented with modules or classes. Each of these enable defining a public interface, by means of which the user can use the abstract data type in question.

The implementation of an abstract data type is hidden behind the interface, and the user need not care about it. Abstract data types are closely related to two terms: information hiding and encapsulation.

Information hiding means hiding the details of the implementation or a limited access to them. The public interface reveals the name of the operation with a comment describing the purpose of the operation. The comment tells also the parameters and the return value of the operation, as well as the meaning of them. This is enough for the user, and such is policy has been used with library functions, too. A user is able to use a library function without knowing its implementation.

Information hiding can concern any function. If a function has a descriptive name, you can think it to cover a certain functionality. For example, if the name of a function is print, it is enough for the caller to know this name and the required parameters.

Encapsulation means that the data and the operations processing the data are bound or packed or wrapped together. This is what we just did in the examples on abstract data types. For example, with the stack implementation we have a stack class (that can be used like a type) and the public methods of the stack class. A class (like a module) enables encapsulation.

Abstract data types, modularity, encapsulation, and information hiding are very closely related to each other. The only difference is the view point, from which we are considering the matter.

A fraction example¶

From the examples of this round, you can find the directory examples/11/fraction containing the class Fraction.

The fraction class is an example on abstract data type. At the same time, it acts as an example on overloading operators.

The class Fraction has two attributes: numerator_ and denominator_. It has overloaded operators for equality comparison, addition, and multiplication.

When we overload addition and multiplication operators, we can use them in the same way as using the corresponding operators for primitive types. For example:

Fraction frac1(2, 3); // creating the fraction 2/3
Fraction frac2(3, 4); // creating the fraction 3/4
Fraction frac3 = frac1 + frac2;

Of course, it would be possible to use the operator function in the same way as any function:

frac3 = frac1.operator+(frac2);

From the above kind of calling convention, we can see that frac3 corresponds to the return value of the function, frac1 is the target object of the call, and frac2 is the parameter. It also reveals that the first operand of addition must be an object, not a fraction literal. We could implement operator overloading without such restriction, but we can do with our solution.

Note that we can combine overloaded operators in usual way, which means that we can have several additions and multiplications in the same expression.

Also the output operator << has been overloaded. Overloading this operator has the benefit that we can print the instances of programmer-defined abstract data types in the same way as other printable values. For example:

Fraction frac(2, 3); // creating the fraction 2/3
cout << "The value of frac is " << frac << endl;

Overloading the operator << is different from overloading arithmetic operators. The operator << is a method of the class ostream (and cout is an instance of that class). Now, the target object is not an object of the Fraction class.

To make the above kind of natural printing way possible, it pays off to implement the overloaded output function as an independent function that is not a method of any class. However, the output function needs the values of the private attributes numerator_ and denominator_ of the Fraction class. For this reason, we need the methods getNumerator and getDenominator.

The first parameter of the output function is the output stream. The second one is an instance of the programmer-defined class, which in this case is an instance of Fraction. Note also that the output function returns the output stream that it has received as a parameter. This enables chaining of the operator <<, which can be seen in the latest code fragment above.

In the same way, we could also overload the input operator >>. However, we have not done so, instead the input is read in the main program. The reason is that in this way, we can check that the user does not give zero as a denominator.

The Fraction class has two private methods: gcd and reduce. The method reduce transforms a fraction into as reduced shape as possible. Such is needed, for example, in equality comparison. In addition, the result of both addition and multiplication is given in the most reduced form.

Reducing a fraction is implemented by first counting the greatest common divisor (gcd) between the numerator and denominator, and then both of these are divided by the counted divisor. Here we need the method gcd that has been implemented recursively.

All in all, the fraction example shows how a programmer-defined class and instances of that class can be used very much the same way as ready-made primitive types.

The implemented Fraction is not perfect. As we have overloaded the addition operator, when it is possible to use + symbol in a usual way, the user of the class can easily assume that they can also use the operator += as usual. However, this is not the case, since that operator has not been overloaded. As an extra exercise, you can implement this operator function.