Skip to content

Section 9: Dynamic Polymorphism Lab

In this discussion, we will implement, test, and evaluate an object-oriented list data structure that uses dynamic polymorphism and then compare it to an object-oriented list that is monomorphic.

1. Logging Into ecelinux with VS Code

Follow the same process as in the last section. Find a free workstation and log into the workstation using your NetID and standard NetID password. Then complete the following steps (described in more detail in the last section):

  • Start VS Code
  • Use View > Command Palette to execute Remote-SSH: Connect Current Window to Host...
  • Enter netid@ecelinux.ece.cornell.edu
  • Use View > Explorer to open folder on ecelinux
  • Use View > Terminal to open terminal on ecelinux

Now clone the GitHub repo we will be using in this section using the following commands:

1
2
3
4
5
6
% source setup-ece2400.sh
% mkdir -p ${HOME}/ece2400
% cd ${HOME}/ece2400
% git clone git@github.com:cornell-ece2400/ece2400-sec09 sec09
% cd sec09
% tree

The repository includes the following files:

  • CMakeLists.txt : CMake configuration script to generate Makefile
  • src/ece2400-stdlib.h : Header file for course standard library
  • src/ece2400-stdlib.cc : Source code for course standard library
  • src/types-dpoly.h : Header file IObject types
  • src/types-dpoly.cc : Source code for IObject types
  • src/SListInt.h : Header file for monomorphic list
  • src/SListInt.cc : Source code for monomorphic list
  • src/SListIObj.h : Header file for dynamic polymorphic list
  • src/SListIObj.cc : Source code for dynamic polymorphic list
  • src/slist-int-adhoc.cc : Ad-hoc test program for monorphic list
  • src/slist-dpoly-adhoc.cc : Ad-hoc test program for dynamic polymorphic list
  • test/types-dpoly-directed.cc : Directed test cases for IObject types
  • test/slist-int-directed-test.cc : Directed test cases for monomorphic list
  • test/slist-dpoly-directed-test.cc : Directed test cases for dynamic polymorphic list
  • eval/slist-int-eval.cc : Evaluation program for list
  • eval/slist-dpoly-eval.cc : Evaluation program for list
  • scripts/slist-*.sh : Bash shell scripts for running evaluation
  • scripts/slist-*.py : Python scripts for plotting

Take a look at the SListIObj.h header file to understand all of the public member functions we will be implementing in this lab.

  • SListIObj(): default constructor
  • ~SListIObj(): destructor
  • SListIObj( const SListIObj& lst ): copy constructor
  • void swap( SListIObj& lst ): swap this list with given list
  • SListIObj& operator=( const SListIObj& lst ): assignment operator
  • void push_front( const IObject& v ): push item on front of list
  • int size() cont: return number of items in the list
  • IObject* at( int idx ) const: return copy of pointer to item at given index (for reading)
  • IObject*& at( int idx ): return reference to pointer to item at given index (for writing)
  • void reverse_v1(): reverse all items in list using algorithm v1
  • void reverse_v2(): reverse all items in list using algorithm v2
  • void print() const: print the list

2. Implementing the Clone Virtual Member Function

Before starting work on a dynamic polymorphic list, we will finish implementing a set of classes that all inherit from the IObject base class. Take a look at the Integer, Double, and Complex classes in src/types-dpoly.h and src/types-dpoly.cc. Implement the clone member function for each of these clases based on the code discussed in lecture.

When you are finished build and run the directed tests like this:

1
2
3
4
5
6
% cd ${HOME}/ece2400/sec09
% mkdir build
% cd build
% cmake ..
% make types-dpoly-directed-test
% ./types-dpoly-directed-test

3. Implementing the Constructor, Destructor, Push Front

Now let's take a look at these functions in src/SListIObj.cc:

  • SListIObj(): default constructor
  • ~SListIObj(): destructor
  • void push_front( const IObject& v ): push item on front of list

We have implemented the default constructor for you. Implement push_front based on the code discussed in lecture. Think critically about how to create a copy of the given IObject. We have started the implementation of the destructor for you. Add the code to delete the node. Do we need to do anything special about the IObject? You can also look at the implementation for a monomorphic list from the previous discussion section in src/SListInt.cc. When you are finished taking a look use adhoc testing to quickly see if your data structure is basically working:

1
2
3
% cd ${HOME}/sec09/src
% g++ -Wall -o slist-dpoly-adhoc slist-dpoly-adhoc.cc SListIObj.cc types-dpoly.cc
% ./slist-dpoly-adhoc

4. Implementing Size and At

Obviously, we want to do more than just ad-hoc testing, but we need some way to check what is in the slist before we can write real directed test cases. Let's take a look at these functions:

  • int size() cont: return number of items in the list
  • IObject* at( int idx ) const: return copy of pointer to item at given index (for reading)
  • IObject*& at( int idx ): return reference to pointer to item at given index (for writing)

We have already implemented these member functions for you, but you should still take a close look. Notice how we have two versions of at: the const version is automatically used by the compiler when reading an item and the non-const version is automatically used by the compiler when writing an item. Keep in mind that at returns an IObject pointer. You cannot copy an IObject since it is an abstract base class; you can only work with pointers and references to an IObject. You can also look at the implementation of at for a monomorphic list from the previous discussion section in src/SListInt.cc.

When you are finished, take a look at the first two directed test cases in slist-dpoly-directed-test.c. Build and run the test cases like this:

1
2
3
4
% cd ${HOME}/ece2400/sec09/build
% make slist-dpoly-directed-test
% ./slist-dpoly-directed-test 1
% ./slist-dpoly-directed-test 2

5. Implementing the Copy Constructor, Swap, and Assignment Operator

Because we need to implement a destructor, the rule of three tells us we also need to implement a copy constructor and assignment operator. We have implemented the copy constructor for you, but spend some time reviewing it. We will be using a "copy-and-swap" pattern to implement the assignment operator, so we need to start by implementing the swap member function. This member functions swaps the internal state between this list and the given list.

Once you have implemented swap you can now use the copy-and-swap pattern which reuses the functionality already implemented in the copy constructor and destructor to implement the overloaded assignment operator:

1
2
3
4
5
6
SListIObj& SListIObj::operator=( const SListIObj& lst )
{
  SListIObj tmp( lst ); // create temporary copy of given list
  swap( tmp );          // swap this list with temporary list
  return *this;         // destructor called for temporary list
}

We first use the copy constructor to make a temporary copy of the given list. We then swap the head pointers between this list and the temporary list. Now this list has a copy of all of the nodes in the given list, and the temporary list has all of the nodes which used to be in this list. When the temporary list goes out of scope, the destructor will handle deleting all of the nodes which used to be in this list. Here is a good article that discusses this pattern:

When you are finished use the corresponding directed test cases to verify your implementation is working:

1
2
3
4
5
6
% cd ${HOME}/sec11/build
% make slist-spoly-directed-test
% ./slist-spoly-directed-test 3
% ./slist-spoly-directed-test 4
% ./slist-spoly-directed-test 5
% ./slist-spoly-directed-test 6

6. Implementing Reverse v1

Take a look at the SListIObj.cc source file to find the reverse_v1 member function. This function should reverse all of the items in the list. Let's use a simple algorithm inspired by the following pseudocode used for reversing an array:

1
2
3
4
5
def reverse( x, n ):
  for i in 0 to n/2:
    lo = i
    hi = (n-1) - i
    swap( x[lo], x[hi] )

You can use the size member function to get the number of items in the list and you can use the at member function to read and write items in the list by index. Think critcally about how to compare and swap IObjects. Can we just swap the pointers? You can also look at the implementation of reverse_v1 for a monomorphic list from the previous discussion section in src/SListInt.cc. When you are finished use the corresponding directed test cases to verify your implementation is working:

1
2
3
4
5
% cd ${HOME}/ece2400/sec09/build
% make slist-dpoly-directed-test
% ./slist-dpoly-directed-test 7
% ./slist-dpoly-directed-test 8
% ./slist-dpoly-directed-test 9

7. Evaluating Reverse v1

We have provided you an evaluation program to quantitatively evaluate the execution time of the linked list data structure and reverse v1 algorithm. Take a look at this evaluation program in slist-dpoly-reverse-v1-eval.c. You can build this evaluation program along with the evaluation program from last week like this:

1
2
3
4
5
6
% cd ${HOME}/ece2400/sec09
% mkdir build-eval
% cd build-eval
% cmake -DCMAKE_BUILD_TYPE=eval ..
% make slist-int-reverse-v1-eval
% make slist-dpoly-reverse-v1-eval

As discussed in the previuod discussion section, you can easily run an evaluation program using a bash script like this:

1
2
3
% cd ${HOME}/ece2400/sec09/build-eval
% source ../scripts/slist-int-reverse-v1-eval.sh
% source ../scripts/slist-dpoly-reverse-v1-eval.sh

We now have a single Python plotting script that can easily plot the result data from any evaluation run with a 0th, 1st, and 2nd order polynomial fit. We also have a single Python plotting script that can plot all of the data on a single plot.

1
2
3
4
% cd ${HOME}/ece2400/sec09/build-eval
% python ../scripts/slist-plot.py ./slist-int-reverse-v1-eval.txt
% python ../scripts/slist-plot.py ./slist-dpoly-reverse-v1-eval.txt
% python ../scripts/slist-plot-all.py

Then you can download the PDF file using VS Code and then open the PDF files on your local workstation or laptop. Do these quantitative results match your qualitative expectations given what you know about the asymptotic time complexity of the reverse v1 algorithm? Do these quantitative results match your qualitative expectations given what you know about the performance of monomorphic vs dynamic polymorphic data structures?

8. Implementing Reverse v2

Let's experiment with an alternative reverse algorithm. This reverse v2 algorithm should use the following steps:

  1. Create temporary singly linked list
  2. Push front all values from this list onto temporary list
  3. Swap this list with the temporary list

You can also look at the implementation of reverse_v2 for a monomorphic list from the previous discussion section in src/SListInt.cc. When you are finished use the corresponding directed test cases to verify your implementation is working:

1
2
3
4
5
% cd ${HOME}/ece2400/sec11/build
% make slist-spoly-directed-test
% ./slist-spoly-directed-test 10
% ./slist-spoly-directed-test 11
% ./slist-spoly-directed-test 12

Your implementation should now pass all tests:

1
2
% cd ${HOME}/ece2400/sec11/build
% make check

9. Evaluating Reverse v2

We have provided you an evaluation program to quantitatively evaluate the execution time of the linked list data structure and reverse v2 algorithm. You can build the evaluation programs for the reverse v2 algorithm on both a monomorphic and dynamic polymorphic list like this:

1
2
3
% cd ${HOME}/ece2400/sec09/build-eval
% make slist-int-reverse-v2-eval
% make slist-dpoly-reverse-v2-eval

We have provided you a Bash script and two Python plotting scripts similar in spirit to what we worked with in a previous section. Let's run the bash script and create the plots.

1
2
3
4
5
6
% cd ${HOME}/ece2400/sec09/build-eval
% source ../scripts/slist-int-reverse-v2-eval.sh
% source ../scripts/slist-dpoly-reverse-v2-eval.sh
% python ../scripts/slist-plot.py ./slist-int-reverse-v2-eval.txt
% python ../scripts/slist-plot.py ./slist-dpoly-reverse-v2-eval.txt
% python ../scripts/slist-plot-all.py

Then you can download the PDF files for both plots using VS Code and then open the PDF file on your local workstation or laptop. Do these quantitative results match your qualitative expectations given what you know about the asymptotic time complexity of reverse v1 vs v2 algorithms?

10. Extensions to Try On Your Own

The code used in this discussion section serves as an excellent framework for continuing to explore object-oriented programming with dynamic polymorphism on your own. Consider copying over the code for a C++ string class presented elsewhere in the course and making this class inherit from IObject. Now you should be able to implement a list of strings data structure or a list that stores a heterogeneous mix of integers, doubles, complex numbers, and strings! Think critically about how you can use dynamic polymorphism to create lists of lists and try it out.