Midterm Examination: Part 2 of 2

Question 1

The goal of this question is to complete the implementation of classes A and B such that they both override properly the method equals that they inherited from the class Object, and that they both implement the interface DeepCopyable that we provide.

Instances of the class A have three instance variables of primitive type int, respectively called a, b and c. These variable are set in the constructor. Instances of the class B have two instance variables of reference type A, respectively called a1 and a2. These variable are set in the constructor, and getters for both variables are available.

We have provided you with a shell implementation of both classes A and B . The declaration of the instance variables, as well as the class constructors and the necessary getters have been provided to you and should not be modi ed. You need to complete these classes to answer the questions below.

Question 1.1    Method equals

The rst task is to override the method equals inherited from the class Object. You need to provide the implementation for both classes A and B. Your implementation should be accurate and reliable, ready to accommodate any possible input. As could be expected, two instances of one of the class are equal if their instance variables are equal.

Question 1.2    Interface DeepCopyable

We have provided the following interface:


public  i n t e r f a c e  DeepCopyable  {

DeepCopyable  deepCopy ( ) ;

}

As you have guessed, the method deepCopy should return a deep copy of the instance on which the method is called. We have introduced the concept of deep copying in assignment 2, and the explanation is repeated here in Appendix A.

The goal of this question is to modify classes A and B so that they both properly implement the interface DeepCopyable, and therefore both provide a reliable deep-copy feature of themselves.

To help you test your solution, we provide you with the following test    le:


public  c l a s s  TestDeepCopy  {

public
s t a t i c  void  main ( S t r i n g [ ]  a r g s ) {
B
b1
=
new B (new A ( 1 , 2 , 3 ) ,
new A ( 4 , 5 , 6 ) ) ;
B
b2
=
new B (new A ( 7 , 8 , 9 ) ,
new A ( 1 0 , 1 1 , 1 2 ) ) ;

System . out . p r i n t l n ( b1 . e q u a l s ( b2 ) ) ;    / /    f a l s e

System . out . p r i n t l n ( b1 . e q u a l s ( b1 . deepCopy ( ) ) ) ;    / /    t r u e

System . out . p r i n t l n ( b1 == b1 . deepCopy ( ) ) ;    / /    f a l s e

System . out . p r i n t l n ( b1 . getA1 ( ) . e q u a l s ( ( ( B ) ( b1 . deepCopy ( ) ) ) . getA1 ( ) ) ) ;    / / t r u e

System . out . p r i n t l n ( b1 . getA1 ( ) = = ( ( ( B ) ( b1 . deepCopy ( ) ) ) . getA1 ( ) ) ) ;    / / f a l s e

}

}

Running that test on a correct implementation will produce the following output:

j a v a c  TestDeepCopy . j a v a

    • j a v a TestDeepCopy f a l s e
true f a l s e true f a l s e

    • 


Important Restrictions for Question 1

You cannot import anything at all.

You cannot use any other class than the ones we provide.

Each question requires that you add a single method to each class. So that is one method to add to both classes for Question 1.1, and one method to add to both classes for Question 1.2. You cannot add any other methods than these two methods, and you cannot add any instance or class variables. For each question, you only add the one method.

You only submit one version of A.java and B.java, each containing your answer to both questions.


Files

A.java (you need to update this one). B.java (you need to update this one).

DeepCopyable.java TestDeepCopy.java

March 2021
ITI 1121
Page 4 of 7
Question 2
(10 marks)


For this question, you are going to develop a specialization (subclass) of ArrayStack. ArrayStack has been already covered in the course lectures. The subclass, named Uniqui ableArrayStack, provides a single additional method, named uniquify().


public  c l a s s    U n i q u i f i a b l e A r r a y S t a c k <E>  extends  ArrayStack <E>  {

public  Stack <E>  u n i q u i f y ( )    {

/ /    A l l    t h e    c o d e    t h a t    you    w r i t e    f o r    Q u e s t i o n  2    g o e s    h e r e !

}

}

The method uniquify() does the following:

It returns a stack which is the same as the Uniqui ableArrayStack instance that the method is called on, except that the returned stack has no immediately consecutive duplicate elements.


To illustrate what “immediately consecutive duplicate elements” are, consider the example stack below:








“e”

“e”

“d”

“d”

“d”

“c”

“b”

“b”

“b”

“a”

“a”








immediately consecutive duplicate elements




immediately consecutive duplicate elements







immediately consecutive duplicate elements




immediately consecutive duplicate elements


More precisely, two stack elements are immediately consecutive duplicate elements, when they are adjacent and have identical content. Having identical content for (non-null) stack elements elem1 and elem2 means that elem1.equals(elem2) is true. You can assume that all stack elements are non-null.

In Question 2, you complete the method uniquify() in the Uniqui ableArrayStack class, so that only one instance of immediately consecutive duplicate elements would be retained. For example, if uniquify() is called over the example stack above (an instance of UniquifiableAr-rayStack<String>), the result should be as shown in the gure on the top of the next page.
March 2021    ITI 1121    Page 5 of 7




“e”

“d”

“c”

“b”

“a”


Note that uniquify() should not have any side e ect on the Uniqui ableArrayStack instance that the method is called on. Furthermore, uniquify() is not meant to deal with non-consecutive duplicate elements. In other words, the stack returned by uniquify() can have non-consecutive duplicate elements. The absence of side e ects on the original stack as well as the carry-over of non-consecutive duplicate elements to the result of uniquify() are illustrated in the example output by Q2Test, presented next.

Example Output

To test your implementation of uniquify(), you can use the Q2Test.java in the template code provided to you. The output from running Q2Test should be as follows:

Original Integer stack: bottom->[0, 1, 1, 1, 2, 2, 3, 3, 3, 4]<-top

Integer stack without immediately consecutive duplicates: bottom->[0, 1, 2, 3, 4]<-top
Original Integer stack (after uniquify): bottom->[0, 1, 1, 1, 2, 2, 3, 3, 3, 4]<-top

Original String stack: bottom->[a, a, b, b, b, c, d, d, d, e, e]<-top

String stack without immediately consecutive duplicates: bottom->[a, b, c, d, e]<-top
Original String stack (after uniquify): bottom->[a, a, b, b, b, c, d, d, d, e, e]<-top

---- Now, testing with some non-consecutive duplicates -----

Original String stack: bottom->[a, b, b, c, a, d, d, e, e, d, d, d, d, b]<-top

String stack without immediately consecutive duplicates: bottom->[a, b, c, a, d, e, d, b]<-top
Original String stack (after uniquify): bottom->[a, b, b, c, a, d, d, e, e, d, d, d, d, b]<-top

Important Restrictions for Question 2

You cannot change either ArrayStack.java or Stack.java. You can change Q2Test.java if you would like to perform additional testing, but for your submission, please leave Q2Test.java just as you found it in the template code.

All your variables should be local variables. You cannot declare any class or instance variables in Uniqui ableArrayStack (or anywhere else for that matter).

The local reference variables in uniquify() as well as in any helper private methods that you may implement can only be of type E (that is, the generic type parameter) or of type Stack<E>. Stated otherwise, you cannot declare any reference variable that has a di erent type than either E or Stack<E>.

You are allowed to use local primitive variables if you nd them necessary, but please note that it is feasible to implement uniquify() without using any local primitive variables.
March 2021    ITI 1121    Page 6 of 7



Files

ArrayStack.java Q2Test.java

Stack.java

UniquifiableArrayStack.java (you need to update this one).


Rules and regulation

Submit your examination through Brightspace. You must do this examination individually.

You must use the provided template classes.

It is your responsibility to make sure that Brightspace has received your examination. Late submissions will not be graded.

Files

Download the archive m2_3000000.zip;

Unzip the  le and rename the directory, replacing 3000000 by your student id;

Add your name and student id in a comment in A.java, B.java and Uniqui ableArrayStack.java;

You must submit a zip le (no other le format will be accepted). The name of the top directory has to have the following form: m2_3000000, where 3000000 is your student number. The name of the folder starts with the letter “m” (lowercase), followed by 2, since this is part 2 of the midterm examination. The segments are separated by the underscore (not the hyphen). There are no spaces in the name of the directory. Your submission must contain the following les, and nothing else. In particular, do not submit the byte-code (.class) les.

README.txt

– A text  le that contains your name and student id

A.java B.java
DeepCopyable.java TestDeepCopy.java ArrayStack.java Q2Test.java

Stack.java

UniquifiableArrayStack.java
March 2021    ITI 1121    Page 7 of 7



    • Shallow copy versus Deep copy

As you know, objects have variables which are either a primitive type, or a reference type. Primitive variables hold a value from one of the language primitive type, while reference variables hold a reference (the address) of another object (including arrays, which are objects in Java).

If you are copying the current state of an object, in order to obtain a duplicate object, you will create a copy of each of the variables. By doing so, the value of each instance primitive variable will be duplicated (thus, modifying one of these values in one of the copy will not modify the value on the other copy). However, with reference variables, what will be copied is the actual reference, the address of the object that this variable is pointing at. Consequently, the reference variables in both the original object and the duplicated object will point at the same address, and the reference variables will refer to the same objects. This is known as a shallow copy: you indeed have two objects, but they share all the objects pointed at by their instance reference variables. The Figure to the le provides an example: the object referenced by variable b is a shallow copy of the object referenced by variable a: it has its own copies of the instances variables, but the references variables title and time are referencing the same objects.

O en, a shallow copy is not adequate: what is required is a so-called deep copy. A deep copy di ers from a shallow copy in that objects referenced by reference variable must also be recursively duplicated, in such a way that when the initial object is (deep) copied, the copy does not share any reference with the initial object. The Figure to the right provides an example: this time, the object referenced by variable b is a deep copy of the object referenced by variable a: now, the references variables title and time are referencing di erent objects. Note that, in turn, the objects referenced by the variable time have also been deep-copied. The entire set of objects reachable from a have been

duplicated.


a




title

time

reminder

15



 “ITI1121 Lecture 2”


start

end




hours

11

minutes

30

a

title

time

reminder

15

b

title

time

reminder

15

 “ITI1121 Lecture 2”


start

end

hours

11

minutes

30


hours

13

minutes

00




b






title

time

reminder

15





 “ITI1121 Lecture 2”


start

end
hours

13

minutes

00


hours

11

minutes

30


hours

13

minutes

00


Figure 1: Example of a shallow copy of objects.    Figure 2: Example of a deep copy of objects.