Description
1 Objectives
1. Experience creating an abstract data type (ADT)1
2. Implement an ADT in C++, using the operator overloading facility of the C++ language
3. Learn about function objects and how to define them
2 Assignment 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 modeled or how the operations are implemented.
Classic ADTs such as rational number and complex number ADTs support many arithmetic,
relational and other operations, making them ideal data types for operator overloading.
However, a search for “class rational c++” reveals many turnkey C++ classes, forcing assignments
designed to provide practice with operator overloading 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 lends itself to operator overloading just as good.
3 Introducing ADT Quad
Quad is an abstract data type, representing a set of values of the form
x1
x2
+
x3
x4
√
2, with x1, x2, x3, x4 all integers and x2 6= 0, x4 6= 0 (1)
and providing a typical set of operations on those values. In this assignment, we will refer to such
values as quad numbers. The integers x1 and x2 represent the real part, and the integers x3 and
x4 represent the quad part, of a quad number.
3.1 Notation
To facilitate presentation of operations on quad numbers, we abstract quad numbers into a
sequence of four ordered integers x1, x2, x3, and x4, corresponding to the same integers in (1).
We use the notations
x1, x2, x3, x4
and
x1
x2
x3
x4
to represent the same quad number, whichever
is more convenient for expressing an operation.
1ADT ≡ Values + Operations − Implementation details of both
1
3.2 Special Quads
Quad x
x1, x2, x3, x4
, x2 6= 0 and x4 6= 0
x Normalized
[−x1, −x2, x3, x4] if x2 < 0
[x1, x2, −x3, −x4] if x4 < 0
[−x1, −x2, −x3, −x4] if x2 < 0 and x4 < 0
x Reduced
x1
gcd(x1, x2)
,
x2
gcd(x1, x2)
,
x3
gcd(x3, x4)
,
x4
gcd(x3, x4)
x Standardized Both Reduced and Normalized
x Conjugated
x1, x2, −x3, x4
, x2 6= 0 and x4 6= 0
Zero
0, z2, 0, z4
, z2 6= 0 and z4 6= 0
Standard zero
0, 1, 0, 1
Identity
1, 1, 0, i4
, i4 6= 0
Standard identity
1, 1, 0, 1
An integer k as a Quad the quad number
k, 1, 0, 1
where gcd(a, b), called the greatest common divisor of the nonzero integers a and b, represents a
positive integer d such that (1) d is a divisor of both a and b, and (2) any divisor of both x and
y is also a divisor of d. For example, gcd(63, 14) = 7, and gcd(30, 45) = 15; thus, the reduced
form of the quad number
63, 14, 30, 45
is
9, 2, 2, 3
.
3.3 Operations on Quads
The basic operations on quad values are listed below, using as operands the quad numbers
x =
x1, x2, x3, x4
and y =
y1, y2, y3, y4
.
Operation Definition
Negation −
x1, x2, x3, x4
=
−x1, x2, −x3, x4
Addition
Subtraction
x1
x2
x3
x4
±
y1
y2
y3
y4
=
x1y2 ± x2y1
x2y2
x3y4 ± x4y3
x4y4
2
Multiplication
x1
x2
x3
x4
∗
y1
y2
y3
y4
=
x1y1x4y4 + 2x3y3x2y2
x2y2x4y4
x1y3y2x4 + y1x3x2y4
x2y2x4y4
Scalar Multiplication k ∗ x =
kx1
x2
kx3
x4
= x ∗ k
Scalar Addition
Scalar Subtraction x ± k =
x1
x2
x3
x4
±
k
1
0
1
=
x1 ± kx2
x2
x3
x4
and k ± x = ±(x ± k)
Inversion x
−1 =
x1x3x
2
4
α
−x2x
2
3x4
α
provided that α = x
2
1x
2
4 − 2x
2
2x
2
3 6= 0
Division x
y = x ∗ y
−1
Scalar Division x
k = x ∗
1
k
=
x1
x2
x3
x4
∗
1
k
0
1
=
x1
kx2
x3
kx4
k 6= 0, x2 6= 0, x4 6= 0
Scalar Division k
x = k ∗ x
−1
Equal? x = y if x1 = y1, x2 = y2, x3 = y3, and x4 = y4
Similar? x is similar to y if x1y2 = y1x2 and x3y4 = y3x4
Norm of x
x1
x2
2
+
x3
x4
2
, a floating-point number measuring x
Absolute value of x
√
Norm of x, a floating-point number
Less than? x < y is true if Norm of x < Norm of y; false, otherwise.
3
4 Your Task
Implement the Quad ADT described above. Your Quad class should have the following members:
1. A container of type std::array
2. A constructor taking four parameters of type long long int, all four with default values.
The zero quad number
0, 1, 0, 1
provides the default values.
3. Defaulted copy constructor, defaulted assignment operator, defaulted virtual destructor
4. Compound assignment operators. Typically, all are implemented as member functions.
quad op quad x += y, x –= y, x *= y, x /= y,
quad op integer x += k, x –= k, x *= k, x /= k
5. Basic arithmetic operators. Not all can be implemented as members. None modifies it
operands. For consistency, all are typically implemented as free functions.
quad op quad x + y , x – y, x * y, x / y,
quad op integer x + k , x – k, x * k, x / k,
integer op quad k + x, k – x, k * x, k / x
6. Relational operators. Not all can be implemented as members. None modifies it operands.
For consistency, all are typically implemented as free functions.
quad op quad x < y, x <= y, x > y, x >= y, x == y, x != y
quad op integer x < k, x <= k, x > k, x >= k, x == k, x != k
integer op quad k < x, k <= x, k > x, k >= x, k == x, k != x
7. An overloaded XOR operator^ such that x^k returns the quad resulting from raising x to
the power k (an integer). Does not modify x.
8. Unary operators ++x, x++, – –x, x– –, +x, and –x. All implemented as members.
9. Subscript operators [ ], both const and non-const versions. If subscript is invalid, must
throw: invalid argument(”index out of bounds”)
10. Function call operator ( ) overload that takes no arguments and returns the absolute
value, a double, of the quad number. This will effectively turn Quad objects like x into
functions–hence the name “function objects.”
11. Overloaded input operator for reading Quad values
12. Overloaded output operator for writing Quad values
13. isSimilar(), inverse(), absoluteValue(), norm(), normalize(), reduce(), conjugate(),
standardize(). Since these members are not as common and well known as arithmetic
and relational operations, we choose to implement them as named member functions, using
meaningful names that reflect their functionality, as opposed to implement them using an
unintuitive and weird looking name that begins with the word “operator” and ends with
a C++ operator symbol.
4
(a) x.isSimilar(y) returns true if x is similar to y; false, otherwise
(b) x.isSimilar(k) returns true if x is similar to Quad(k); false, otherwise
(c) x.inverse() returns the inverse of x
(d) x.absoluteValue() returns the absolute value of x, a double value
(e) x.norm() returns the norm of x, a double value
(f) x.normalize() normalizes x; returns void
(g) x.reduce() reduces x; returns void
(h) x.standardize() both reduces and normalizes x; returns void
(i) x.conjugate() returns the conjugate of x
5 Requirements
1. Quad numbers such as x =
x1, x2, x3, x4
must be normalized so that x2 and x4 are
positive.
2. Quad operations can produce a quad number whose integer components are huge in magnitude, resulting in integer overflow. Therefore, to reduce possibility of integer overflow,
operations that create or modify quad numbers must reduce the resulting quad numbers.
6 Basic guidelines
Use the following guidelines2
to choose to either implement operators as a member function or a
non-member function:
Operator Recommended Implementation
=, ( ), [ ], − > must be member
All unary operators member
Compound assignment operators member
All other binary operators non-member
7 Deliverables
1. Header files: Quad.h
2. Implementation files: Quad.cpp, quad test driver.cpp
3. A README.txt text file (as described in the course outline).
2Rob Murray, C++ Strategies & Tactics, Addison-Wesley, 1993, page 47.
5
8 Sample Test Driver
1 # include
2 # include
3 # include
4 # include
6 # include ” Quad .h”
7 using std :: cout ;
8 using std :: endl ;
9
10 /*
11 Tests class Quad . Specifically , tests constructors , compound assignment
12 operator overloads , basic arithmetic operator overloads , unary + , unary -,
13 pre/post – increment / decrement , subscripts , function objects ,
14 input / output operators , isSimilar , absValue , and equality relational operators .
15
16 @return 0 to indicate success .
17 */
18 void print ( const std :: string item , const Quad & q)
19 {
20 cout << std :: left << std :: setw (20) << item << q << endl ;
21 }
22 int main ()
23 {
24 // cout << " sizeof ( long long int ) = " << sizeof ( long long int ) << ’\n ’;
25 // cout << " Minimum value for long long int : "
26 // << std :: numeric_limits < long long int >:: min () << ’\n ’;
27 // cout << " Maximum value for long long int : "
28 // << std :: numeric_limits < long long int >:: max () << ’\n ’;
29 // Minimum value for 8-byte long long int : -9223372036854775808
30 // Maximum value for 8-byte long long int : 9223372036854775807
31
32 Quad zero ; // defaluts to the zero quad [0,1,0,1]
33 print (" Quad zero ", zero );
34 assert ( zero == Quad (0,1,0,1));
35
36 Quad one(1); // [1,1,0,1]
37 print (" Quad identity (1)", one);
38 assert ( one == Quad (1, 1, 0, 1));
39
40 Quad half (1,2); // [1,2,0,1]
41 print (" Quad half (1,2)", half );
42 assert ( half == Quad (1, 2, 0, 1));
43
44 Quad q0;
45 print (" Quad q0", q0);
46 assert (q0 == zero );
6
47
48 Quad q1(2); // defaluts to the zero quad [2,1,0,1]
49 print (" Quad q1(2)", q1);
50 assert (q1 == Quad (2, 1, 0, 1));
51 Quad q2(2,3); // defaluts to [2,3,0,1]
52 print (" Quad q2(2,3)", q2);
53 assert (q2 == Quad (2, 3, 0, 1));
54
55 Quad q3(2, 3, 4); // defaluts to [2,3,4,1]
56 print (" Quad q3(2,3,4)", q3);
57 assert (q3 == Quad (2, 3, 4, 1));
58
59 Quad q4(2, 3, 4, 5); // [2,3,4,5]
60 print (" Quad q4(2, 3, 4, 5)", q4);
61 assert (q4 == Quad (2, 3, 4, 5));
62
63 assert (q0 + one == one );
64 assert (q0 * one == zero );
65 assert ( one * one == one );
66 assert ( one + one == Quad (2));
67 assert ( Quad (2) - one == one );
68 assert ( Quad (1, 2). isSimilar ( Quad (10, 20)));
69 assert ( Quad (1, 2) == Quad (10, 20)); // Quad ’s ctor always standardizes the constructed quad
70 assert ( Quad (1, 2) == Quad (1, 2));
71
72 Quad q11(100, -100, -1000, -1000);
73 print ("q11", q11);
74 assert (q11 == Quad (-1, 1, 1, 1));
75 q11[1] = 1;
76 assert (q11 == Quad (1, 1, 1, 1));
77 Quad q23(10, 5, 6, 2);
78 assert (q23 == Quad (2,1,3,1));
79 Quad q22{ q23 - Quad (0,10,10,10) };
80 assert (q22 == Quad (2, 1, 2, 1));
81 assert (q22 - q11 == q23 - q22 + one );
82
83 // additions and subtractions
84 Quad q01234 = q0 + q1 + q2 + q3 + q4;
85 print ("q01234", q01234);
86 Quad qs01234 = -q0 - q1 - q2 - q3 - q4;
87 print ("qs01234", qs01234);
88 assert (q01234 == -qs01234);
89 Quad m01234 = 5LL * q0 + 4LL*q1 + 3LL*q2 + 2LL * q3 + 1LL * q4;
90 print ("m01234", m01234);
91 Quad n01234 = q0 * 5LL + q1 * 4LL + q2 * 3LL + q3 * 2LL + q4 * 1LL;
92 print ("n01234", n01234);
93 assert (m01234 == n01234);
94
95 // mutiplications , division
96 Quad qm1234 = q1 * q2 * q3 * q4;
97 print ("qm1234", qm1234);
98 Quad qmr1234 = q4 * q3 * q2 * q1;
99 print ("qmr1234", qmr1234);
100 assert (qm1234 / q4 / q1 == (q3/3LL + q3 / 3LL + q3 / 3LL) * (q2/ 2LL + q2 / 2LL));
7
101
102 cout << setw (20) << "q4. norm () = " << q4. norm () << endl ;
103 double size_of_q 4 = q4; // quad to double ( not double to quad ! )
104 cout << setw (20) << " size of q4 = " << size_of_q 4 << endl ;
105 cout << setw (20) << " conjugate of q4 = " << q4. conjugate () << endl ;
106 Quad q5{ qmr 1234 }; //
107 print (" Quad q5{ qmr1234 }", q5);
108
109 // inverse
110 Quad q5 _inverse { q5. inverse () };
111 print (" Quad q5 _inverse ", q5 _inverse );
112 assert (q5 _inverse * q5 == one );
113 assert (q5 == one / q5 _inverse );
114 assert (q5 _inverse == one / q5);
115
116 // operator []
117 Quad q6{};
118 q6[1] = 10;
119 q6[2] = -20;
120 q6[3] = 0;
121 q6[4] = 40;
122 print ("q6", q6);
123 q6. normalize ();
124 print ("q6 normalized ", q6);
125 q6. reduce ();
126 print ("q6 reduced ", q6);
127
128 // operator ++ , --, both versions
129 ++q6;
130 print ("++q6", q6);
131 q6 += half ;
132 print ("q6 += half ", q6);
133 assert (q6 == one);
134 q6++;
135 print ("q6++", q6);
136 assert (q6 == one + one );
137 q6 - -;
138 print ("q6 --", q6);
139 assert (q6 == one);
140 --q6;
141 print (" --q6", q6);
142 assert (q6 == zero );
143
144 // operator ^ to raise a quad to a positive integer power
145 Quad q7{ half };
146 print ("q7", q7);
147 q7 = half ^ 1;
148 print ("q7 = half ^ 1", q7);
149 q7 = half ^ 2;
150 print ("q7 = half ^ 2", q7);
151 q7 = half ^ 3;
152 print ("q7 = half ^ 3", q7);
8
153 q7 = half ^ 4;
154 print ("q7 = half ^ 4", q7);
155 q7 = half ^ 5;
156 print ("q7 = half ^ 5", q7);
157
158 // operator >>
159 Quad input_quad {};
160 cin >> input_quad ;
161 print (” input_quad “, input_quad );
162 // operator ^ to raise a quad to a positive integer power
163 Quad q8{};
164 print (“q8”, q8);
165 q8 = input_quad ^ 1;
166 print (“q8 = input_quad ^ 1”, q8);
167 q8 = input_quad ^ 2;
168 print (“q8 = input_quad ^ 2”, q8);
169 q8 = input_quad ^ 3;
170 print (“q8 = input_quad ^ 3”, q8);
171 q8 = input_quad ^ 4;
172 print (“q8 = input_quad ^ 4”, q8);
173 q8 = input_quad ^ 5;
174 print (“q8 = input_quad ^ 5”, q8);
175
176 // operator ^ to raise a quad to a negative integer power
177 Quad q9{};
178 print (“q9”, q9);
179 q9 = input_quad ^ (-1);
180 print (“q9 = input_quad ^ (-1)”, q9);
181 q9 = input_quad ^ (-2);
182 print (“q9 = input_quad ^ (-2)”, q9);
183 q9 = input_quad ^ (-3);
184 print (“q9 = input_quad ^ (-3)”, q9);
185 q9 = input_quad ^ (-4);
186 print (“q9 = input_quad ^ (-4)”, q9);
187 q9 = input_quad ^ (-5);
188 print (“q9 = input_quad ^ (-5)”, q9);
189
190 assert (q8 * q9 == one);
191
192 cout << " Test completed successfully !" << endl ;
193 return 0;
194 }
9
Output
1 Quad zero [0, 1, 0, 1]
2 Quad identity (1) [1, 1, 0, 1]
3 Quad half (1,2) [1, 2, 0, 1]
4 Quad q0 [0, 1, 0, 1]
5 Quad q1(2) [2, 1, 0, 1]
6 Quad q2(2,3) [2, 3, 0, 1]
7 Quad q3(2,3,4) [2, 3, 4, 1]
8 Quad q4(2, 3, 4, 5) [2, 3, 4, 5]
9 q11 [ -1, 1, 1, 1]
10 q01234 [4, 1, 24, 5]
11 qs01234 [ -4, 1, -24, 5]
12 m01234 [12, 1, 44, 5]
13 n01234 [12, 1, 44, 5]
14 qm1234 [1232, 135, 64, 15]
15 qmr1234 [1232, 135, 64, 15]
16 q4. norm () = 1.08444
17 size of q4 = 1.04137
18 conjugate of q4 = [2, 3, -4, 5]
19 Quad q5{ qmr 1234 } [1232, 135, 64, 15]
20 Quad q5 _inverse [10395, 53392, -1215, 13348]
21 q6 [10, -20, 0, 40]
22 q6 normalized [ -10, 20, 0, 40]
23 q6 reduced [ -1, 2, 0, 1]
24 ++q6 [1, 2, 0, 1]
25 q6 += half [1, 1, 0, 1]
26 q6++ [2, 1, 0, 1]
27 q6 -- [1, 1, 0, 1]
28 --q6 [0, 1, 0, 1]
29 q7 [1, 2, 0, 1]
30 q7 = half ^ 1 [1, 2, 0, 1]
31 q7 = half ^ 2 [1, 4, 0, 1]
32 q7 = half ^ 3 [1, 8, 0, 1]
33 q7 = half ^ 4 [1, 16, 0, 1]
34 q7 = half ^ 5 [1, 32, 0, 1]
35 About to create the quad [a, b, c, d]
36 Enter four numbers a, b, c, d, in that order :
37 1 2 3 4
38 input_quad [1, 2, 3, 4]
39 q8 [0, 1, 0, 1]
40 q8 = input_quad ^ 1 [1, 2, 3, 4]
41 q8 = input_quad ^ 2 [11, 8, 3, 4]
42 q8 = input_quad ^ 3 [29, 16, 45, 32]
43 q8 = input_quad ^ 4 [193, 64, 33, 16]
44 q8 = input_quad ^ 5 [589, 128, 843, 256]
45 q9 [0, 1, 0, 1]
46 q9 = input_quad ^ (-1)[ -4, 7, 6, 7]
47 q9 = input_quad ^ (-2)[88, 49, -48, 49]
48 q9 = input_quad ^ (-3)[ -928, 343, 720, 343]
49 q9 = input_quad ^ (-4)[12352, 2401, -8448, 2401]
50 q9 = input_quad ^ (-5)[ -150784, 16807, 107904, 16807]
51 Test completed successfully !
10
9 Evaluation Criteria
Evaluation Criteria
Functionality Testing correctness of execution of your program, Proper implementation of all specified requirements, Efficiency
60%
OOP style Encapsulating only the necessary data inside your objects, Information hiding, Proper use of C++ constructs and facilities. No
use of operator new and operator delete. No C-style coding and
memory functions such as malloc, alloc, realloc, free, etc.
20%
Documentation Description of purpose of program, Javadoc comment style for
all methods and fields, comments on non-trivial pieces of code in
submitted programs
10%
Presentation Format, clarity, completeness of output, user friendly interface 5%
Code readability Meaningful identifiers, indentation, spacing, localizing variables 5%