COMP5421- Assignment 3: Abstract Data Type (ADT) Solved

Objectives
To experience creating an abstract data type (ADT)

To implement an ADT in C++, using the operator overloading facility of the C++ language To learn how to turn objects of a class into “function objects”

To learn how to convert objects of a class to objects of unrelated types (e.g., Foo to bool)

2       Background
A data type represents a set of data values sharing common properties. An abstract data type (ADT) specifies a set of operations on a data type, independent of how the data values are actually represented or how the operations are implemented.

Classic ADTs representing mathematical entities such as rational number and complex number ADTs support many arithmetic, relational and other operations, making them ideal data types for operator overloading.

Since there is no shortage of code for C++ classes representing rational and complex numbers, assignments designed to provide practice with operator overloading tend to get a bit creative with their choice of data types; ideally, a data type that is not as ubiquitous as rational and complex number ADTs, but one that lends itself to operator overloading just as good.

3        Mat2x2 ADT
Mat2x2 is an ADT that encapsulates a “2×2 matrix”, a simple mathematical entity of the form

, where the numbers a, b, c, and d represent the “value” of a 2 × 2 matrix data type.

For example, the numbers 4, 8, 7, and 3 together can represent the value of the 2 × 2 matrix

.

3.1        Notation
 a real number, a multiplicative scalar  a real number, an additive scalar

3.2        Operations
Scalar Multiplication

Scalar Addition Scalar Subtraction

addition

subtraction

multiplication

determinant

inverse                              A−1 = inv(A) = inv ,            det(A) 6= 0

division
A/B = AB−1,              det B 6= 0
Norm
p

||A|| = norm(A) =          a2 + b2 + c2 + d2
Relational Equality           .

 
The symbol  denotes a tolerance, a small positive amount the value ||A − B|| can change and still be acceptable that A is equal to B.
Relational Inequality
A < B if ¬(A = B) and ||A|| < ||B||
where ¬ denotes the negation operator.

Recall that the definitions of the operators < and = on objects X and Y are sufficient for deriving the definitions of the other four relational

 

operators >, ≥, 6=, and ≤:

X > Y ≡ Y < X

X ≥ Y ≡ ¬(X < Y )
X 6= Y ≡ ¬(X = Y )

X ≤ Y ≡ X < Y or X = Y

 

       4       Your Task
Implement the Mat2x2 ADT above using a C++ class, called Mat2x2, that uses one of the representations listed in section 5 to store the underlying data as private member(s).

The public interface of your Mat2x2 class must include the following member functions:

Constructors:
explicit Mat2x2(double = 0, double = 0, double = 0, double = 0);

Mat2x2(const array<double, 4> &);
// using std::array;
Mat2x2(const array<array<double, 2>, 2>&); // using std::array;

Mat2x2(const initializer_list<double>);
// using std::initializer_list;
Defaulted copy/move constructors, copy/move assignment operators, and destructor.
norm(), returns the norm of the calling object
inverse(), returns the inverse of the calling object
det(), returns the determinant of the calling object
                    4.1          Member Operator Overload Functions
Compound assignment operator overloads.
Mat2x2 op Mat2x2 x+=y, x-=y, x*=y, x/=y

Mat2x2 op double x+=k, x-=k, x*=k, x/=k

Unary operators ++x, x++, +x, --x, x--, -x, where x is a Mat2x2
An overloaded XOR operator^ such that x^k returns the Mat2x2 object resulting from raising x to the power k (an integer). It does not modify x.
Subscript operators [ ], both const and non-const If subscript is invalid, must throw: invalid argument("index out of bounds")
These operator overloads provide direct access to the underlying data members, effectively eliminating the need for friend functions.

operator bool() const Returns whether or not the invoking object has inverse. For example, if x is a Mat2x2 object, it returns true if , and returns false
                    4.2        Function objects
Overloading the function call operator, these overloads effectively turn Mat2x2 objects into functions; hence the name “function object.”

double operator()()const Returns the norm of the invoking Mat2x2 For example, if x is a Mat2x2 object, then x() returns x.norm().
double& operator()(size t r, size t c)
Returns an lvalue reference to the entry at row r and column c.

Since it would be more intuitive for humans to start row and column indexing at 1, this function must ensure that the values of r and c are 1-based.

For example, if x stores the matrix , then x(i, j) should return a reference to xij, i = 1,2, j = 1,2.

If r or c is invalid, then this function must throw an exception as shown below:

if (r < 1 || r > 2) throw invalid_argument("row index out of bounds"); if (c < 1 || c > 2) throw invalid_argument("column index out of bounds");
1

2

4.3 static Members
static double tolerance; // initial value = 1.0E-6 static void setTolerance(double tol); static double getTolerance();
1

2

3

See Relational Equality in section 3.2 where “tolerance” is defined.

                    4.4           Non-Member Operator Overload Functions
Overloaded extraction operator >> for reading Mat2x2 values
Overloaded insertion operator << for writing Mat2x2 values
Basic arithmetic operators. None modifies it operands. Not all can be implemented as members (which ones?). For consistency, all are typically implemented as free functions.
Mat2x2 op Mat2x2
x+y, x-y, x*y, x/y
Mat2x2 op double
x+k, x-k, x*k, x/k
double op Mat2x2
k+y, k-y, k*y, k/y
Relational operators. None modifies it operands. For consistency, all are typically implemented as free functions.
Mat2x2 op Mat2x2 x<y, x<=y, x>y, x>=y, x==y, x!=y

       5            Alternative Representations for a 2×2 Matrix
Applying the OOP’s principle of information hiding, an implementation of an ADT can optimize both representation of the data type and implementation of the operations without affecting the client code.

However, since an ADT does not depend on the representation of the data type it specifies, the first order of business for any implementation of an ADT is to define concrete representation of the data type so that the operations on the type can be implemented.

The examples below show three common representations of a 2 × 2 matrix :

Eaxmple 1: Viewing the 2 × 2 matrix as four individual elements a, b, c, and d:

double a; // top-left double b; // top-right double c; // bottom-left double d; // bottom-right
1

2

3

4

For the benefit of human readers of the code, such representation must explicitly document the correspondence between the matrix elements and the variable a, b, c, and d.

Eaxmple 2: Viewing the 2 × 2 matrix as a sequence (y0,y1,y2,y3)

For storing and managing any sequence of const size, modern C++ provides a smart array class template in the <array> header file:

std::array <double, 4> y; // an array of 4 doubles
1

std::array provides a rich set of useful methods as well as supporting the familiar array notation y[0], y[1], y[2], and y[3].

This representation too must document the correspondence between the matrix elements and the variable y[0], y[1], y[2], and y[3].

            Eaxmple 3: Viewing the 2 × 2 matrix as , or as         , as an

array of two rows, each in turn an array of two elements.

std::array< std::array <double, 2>, 2> x;

// x is an array of size 2;

// each element of x is an array of 2 doubles;
1

2

3

Note that x is a std::array of std::arrays, representing a two-dimensional table or matrix of doubles.

Overloading the subscript operator [], std::array provides the familiar array notation. Specifically, the two elements (the rows) x[0] and x[1] of the 2D-array x are each of type std::array<double, 2>, and as such, x[0]’s two elements on the first row are x[0][0], and x[0][1], and x[1]’s two elements on the second row are x[1][0], and x[1][1].

       5.1            What About Multi-Dimensional Raw Arrays?

C++ does not provide a special multi-dimensional raw array type. Instead, C++ provides only one-dimensional array type, but it allows the array elements themselves to be “one-dimensional arrays”.

For example, denoting a two-dimensional 5 × 3 array of 5 rows and 3 columns, the declaration double A[5][3] means that A is a one-dimensional array of 5 elements, each of which, in turn, is an array of 3 doubles. Specifically,

A[0] points to an array of 3 elements A[0][0], A[0][1], A[0][2] on row 1,

A[1] points to an array of 3 elements A[1][0], A[1][1], A[1][2] on row 2, and in general, A[r] points to an array of 3 elements A[r][0], A[r][1], A[r][2] on row r+1.

Similarly, the declaration double B[3][4][5] declares B as an array of size 3 whose elements are each arrays of size 4 whose elements are each arrays of 5 doubles.

Question 1

Write a declaration for a function named process2D that is to receive and process a raw array of 7 raw arrays, each of 5 doubles.

Question 2

Write a declaration for a function named process3D that is to receive and process a three-dimensional 5 × 3 × 7 array of integers.

       5.2             Prefer std::arrays to Raw Arrays
Given std::array<T,n> container, a smart class template modeling an array of fixed size n and elements of type T, there is really no good reason to use raw arrays in C++.

The justification for this is that a std::array<T,n> object stores and can tell the size of the array, provides bounds checking facilities, can be passed as an argument to a function without decaying to a pointer, can be used by any algorithm designed to work with C++ container classes, provides the familiar raw array notation (by overloading the [] operator), and more.