Content

Introduction to ADTs in C ADT Initialization and Representation Invariants Interfaces and Implementations Abstraction Layers Testing an ADT Testing with stringstreams <- Go Back

EECS 280: Programming and Introductory Data Structures

Section 08

Abstract Data Types in C

University of Michigan at Ann Arbor

Last Edit Date: 02/06/2023

Disclaimer and Term of Use:

1. We do not guarantee the accuracy and completeness of the summary content. Some of the course material may not be included, and some of the content in the summary may not be correct. You should use this file properly and legally. We are not responsible for any results from using this file

2. This personal note is adapted from Professor Amir Kamil, Andrew DeOrio, James Juett, Sofia Saleem, and Saquib Razak. Please contact us to delete this file if you think your rights have been violated.

3. This work is licensed under a Creative Commons Attribution 4.0 International License.

---

Introduction to ADTs in C

The concept of abstraction can be applied to data as well. An abstract data type (ADT) separates the interface of a data type from its implementation, and it encompasses both the data itself as well as functionality on the data. An example of an ADT is the string type in C++, used in the following code:

1     string str1 = "hello";
2     string str2 = "jello";
3     cout << str1 << endl;
4     if (str1.length() == str2.length()) {
5       cout << "Same length!" << endl;
6     }

A string is an example of a full-featured C++ ADT, providing customized initialization, overloaded operations such as the stream-insertion operator, member functions, and so on.

The C language only has support for structs with data members (i.e. member variables). While this is sufficient to represent the data of an ADT, the functions that operate on the ADT must be defined separately from the struct. The following is the data definition of an ADT to represent triangles:

 1     struct Triangle {
 2       double a;
 3       double b;
 4       double c;
 5     };
 6
 7     int main() {
 8       Triangle t1 = { 3, 4, 5 };
 9       Triangle t2 = { 2, 2, 2 };
10     }

Try it out:

Open in new window

The Triangle struct contains three member variables, one for each side of the triangle, each represented by a double. The example in main() creates and initializes two Triangle structs, resulting in the following memory layout:

An ADT also includes functions that operate on the data. We can define functions to compute the perimeter of a triangle or to modify it by scaling each of the sides by a given factor:

 1     // REQUIRES: tri points to a valid Triangle
 2     // EFFECTS:  Returns the perimeter of the given Triangle.
 3     double Triangle_perimeter(const Triangle *tri) {
 4       return tri->a + tri->b + tri->c;
 5     }
 6
 7     // REQUIRES: tri points to a valid Triangle; s > 0
 8     // MODIFIES: *tri
 9     // EFFECTS:  Scales the sides of the Triangle by the factor s.
10     void Triangle_scale(Triangle *tri, double s) {
11       tri->a *= s;
12       tri->b *= s;
13       tri->c *= s;
14     }

Our naming convention for functions that are part of a C-style ADT is to prepend the function name with the name of the ADT, Triangle in this case. The first parameter is a pointer to the actual Triangle object the function works on. If the object need not be modified, we declare the pointer as a pointer to const.

The following demonstrates how to use the Triangle ADT functions:

1     int main() {
2       Triangle t1 = { 3, 4, 5 };
3       Triangle_scale(&t1, 2);                   // sides are now 6, 8, 10
4       cout << Triangle_perimeter(&t1) << endl;  // prints 24
5     }

Try it out

Open in new window

The code creates a Triangle as a local variable and initializes it with sides 3, 4, and 5. It then scales the sides by a factor of 2 by calling Triangle_scale(). Since that function takes a pointer to the actual triangle, we use the address-of operator to obtain and pass the address of t1, as shown below

ADT Initialization and Representation Invariants

An essential component of proper ADT design is the use of representation invariants to express conditions that differentiate valid data (e.g. a Triangle with sides 3, 4, and 5) from invalid, nonsense values (e.g. one of the side lengths is -10).

Example 1

1     const int MAX_MATRIX_WIDTH = 500;
2     const int MAX_MATRIX_HEIGHT = 500;
3
4     struct Matrix{
5       int width;
6       int height;
7       int data[MAX_MATRIX_WIDTH * MAX_MATRIX_HEIGHT];
8     };

Some possible representation invariants:

• 0 < width <= MAX_MATRIX_WIDTH

• 0 < height <= MAX_MATRIX_HEIGHT

• The first width * height elements of data are in valid information, the rest is junk

• Elements are laid out in row-major order

Example 2

1     const int MAX_INTENSITY = 255;
2     
3     struct Image {
4       int width;
5       int height;
6       Matrix red_channel;
7       Matrix green_channel;
8       Matrix blue_channel;
9     }

Some possible representation invariants:

• 0 < width <= MAX_MATRIX_WIDTH

• 0 < height <= MAX_MATRIX_HEIGHT

• 0 <= values stored in channels <= 255

• width / height members of all channel matrices are the same as the width / height of image

We usually use assert() to test these representation invariants.

Interfaces and Implementations

We adhere to the convention of only interacting with an ADT through its interface. Usually, this means that we do not access the data members of an ADT in outside code.

However, occasionally we have the need for an ADT that provides no more functionality than grouping its members together.

Such an ADT is just plain old data (POD), without any functions that operate on that data, and we define its interface to be the same as its implementation.

The following is an example of a Pixel struct used as a POD:

 1     struct Pixel {
 2       int r; // red
 3       int g; // green
 4       int b; // blue
 5     };
 6
 7     int main() {
 8       Pixel p = { 255, 0, 0 };
 9       cout << p.r << " " << p.g << " " << p.b << endl;
10     }

The Pixel ADT consists of just a data representation with no further functionality. Since it is a POD, its interface and implementation are the same, so it is acceptable to access its members directly.

Abstraction Layers

As with procedural abstraction, data abstraction is also defined in layers, with each layer interacting solely with the interface of the layer below and not its implementation.

For example, we can represent an image using three matrices, one for each color channel.

Any code that uses an image relies on the image interface, without needing to know that it is implemented over three matrices.

Each matrix in turn can be represented using a single-dimensional array. Code that uses a matrix relies on the 2D abstraction provided by the interface without needing to know that it is implemented as a 1D array under the hood.

Testing an ADT

Adhering to the interface often means that we can’t test each ADT function individually. For instance, we cannot test Triangle_init() in isolation; instead, we can test it in combination with the side accessors (e.g. Triangle_side1()) to determine whether or not the initialization works correctly.

Example:

1     // REQUIRES: mat points to a valid Matrix
2     //           0 <= row && row < Matrix_height(mat)
3     //           0 <= column && column < Matrix_width(mat)
4     //
5     // MODIFIES: (The returned pointer may be used to modify an
6     //            element in the Matrix.)
7     // EFFECTS:  Returns a pointer to the element in the Matrix
8     //           at the given row and column.
9     int* Matrix_at(Matrix* mat, int row, int column) {

The following two rows are bad examples
Type Prohibited	ASSERT_EQUAL(*Matrix_at("cat", 2, 2), 42);
Requires Prohibited	ASSERT_EQUAL(*Matrix_at（$\begin{bmatrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}$, 2, -1), 42);
The following three rows are good examples
Simple	ASSERT_EQUAL($\begin{bmatrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}$, 1, 1), 5);
Special (edge)	ASSERT_EQUAL($\begin{bmatrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}$, 2, 2), 9);
Stress	Matrix_init(big, 400, 400); Matrix_fill(big, 1); ASSERT_TRUE(Matrix_equal(big, $\begin{bmatrix}1 & \dots & 1 \\ \vdots & \ddots & \vdots \\ 1 & \dots & 1 \end{bmatrix}$));

Testing with stringstreams

In C++, input streams generally derive from istream. We will see what this means specifically when we look at inheritance and polymorphism in the future. For our purposes right now, this means that we can pass different kinds of input-stream objects to a function that takes in a reference to an istream.

Similarly, output streams generally derive from ostream, and we can pass different kinds of output-stream objects to a function that takes in a reference to an ostream.

When writing unit tests, we often want the tests to be standalone without requiring access to external data. For tests that work with streams, we can use string streams rather than standard input/output or file streams. To use a string stream, we #include <sstream>. We can then use an istringstream as an input stream, and an ostringstream as an output stream.

The following is an example of using an istringstream to represent input data for testing a function that takes in an input stream:

 1     TEST(test_image_basic) {
 2       // A hardcoded PPM image
 3       string input = "P3\n2 2\n255\n255 0 0 0 255 0 \n";
 4       input += "0 0 255 255 255 255 \n";
 5
 6       // Use istringstream for simulated input
 7       istringstream ss_input(input);
 8       Image *img = new Image;
 9       Image_init(img, ss_input);
10
11       ASSERT_EQUAL(Image_width(img), 2);
12       Pixel red = { 255, 0, 0 };
13       ASSERT_TRUE(Pixel_equal(Image_get_pixel(img, 0, 0), red));
14       delete img;
15     }

We start with a string that contains the actual input data and then construct an istringstream from that. We can then pass that istringstream object to a function that has a parameter of type istream &. When that function extracts data, the result will be the data from the string we used to construct the istringstream.

We can similarly use an ostringstream to test a function that takes an output stream:

 1     TEST(test_matrix_basic) {
 2       Matrix *mat = new Matrix;
 3       Matrix_init(mat, 3, 3);
 4       Matrix_fill(mat, 0);
 5       Matrix_fill_border(mat, 1);
 6
 7       // Hardcoded correct output
 8       string output_correct = "3 3\n1 1 1 \n1 0 1 \n1 1 1 \n";
 9
10       // Capture output in ostringstream
11       ostringstream ss_output;
12       Matrix_print(mat, ss_output);
13       ASSERT_EQUAL(ss_output.str(), output_correct);
14       delete mat;
15     }

We default construct an ostringstream object and pass it to a function with a parameter of type ostream &. The ostringstream will internally capture the data that the function inserts into it. We can then call .str() on the ostringstream to obtain a string that contains that data, which we can then compare to another string that contains the expected output.

© Sample Academy