Exercise 6: Design II

This exercise will help you practice and demonstrate your ability to perform basic design tasks using multiple forms of polymorphism to address design constraints. Again note that these tasks are not focused on syntax or algorithms but rather on problem solving.

Once again, there are rules.

• You are not allowed to create any inheritance hierarchy with more than two levels, a base class and derived classes.
• You may not use parts of the standard library apart from things in <algorithms>, <numeric>, <memory>, <optional>, <set>, <unordered_map>, <unordered_set>, <queue>, <vector>, <type_traits> and <iostream>.
• You may not use new or delete.
• All code must compile without errors or leaks.
• You may not use using namespace anywhere.
• You may not use dynamic casts anywhere.
• You may not use std::any.
• Additional rules may be added on a per task basis.

Note also that some tasks may be graded qualitatively. For those tasks, producing functioning code alone may not suffice. Instead, you must also show good judgement and design in your code in order to receive full credit. Consider the guidelines we have discussed in class.

A template for the project is available here. You should not add new files to the template or they will not be graded. All of your solutions should modify code in the lib/solutions directory. This helps automated checking for adhering to the rules.

Note as well that normal plagiarism detection will be applied. Do not share your code with or show your code to other students.

Task 1 – Cleanly adding structure to a crazy world

In this task you will focus on combining multiple forms of polymorphism in order to make a design that provides a clear and clean API to the user. Successfully completing the task will involve combining multiple forms of polymorphism, but identifying where to use different forms can largely be done in an incremental fashion.

You must design a Structure class. A Structure is simply a container that can hold a sequence of heterogeneous elements. This initially sounds trivial, but the interface of a Structure should provide for flexible and easy usage. Achieving those properties adds internal complexity. In addition, Structures should be assignable and copyable while maintaining ownership over their contents. A Structure should support the following operations:

• Creation – An empty Structure can be created simply by using the no-args constructor.
• Assignment – Given an existing Structure s, s can be reassigned via an assignment operator, e.g. s = Structure{};
• Copying – Given an existing Structure s, s can be copied into other Structures, e.g. t = s and Structure t = s. Each copy of the Structure should be fully distinct, and changes to the contents of one structure should not affect the contents of other structures (both the structure and contents are copied).
• Adding elements – The add method should accept any type of argument that (1) is itself both copyable and equality comparable and (2) separately has a printElement overload for the corresponding type. A compiler error should result from cases where the argument is not copyable, but there are no constraints on the nature of this compiler error. The argument to the add method is then copied to the end of the Structure.
• Printing elements – The print method should take an output stream, e.g. std::cout, and call printElement for each item in the Structure in order. Between each element, the text "BETWEEN\n" should be printed to the stream. The printElement function for a given type will take two arguments, an output stream (std::ostream) and the element to print. You can find examples of these within the unit tests. Observe that printElement is an overloaded function must be resolved via the static type of its arguments. A newline should be printed to the given stream after each call to printElement.
• Equality Comparison – Two Structures can be compared via the == operator. If their contents are equal by value comparison of their individual elements, then the operator returns true. Empty Structures are trivially equal. Comparing against any Structure with more than 13 elements always returns false. Otherwise two Structures are nonequal. Surprisingly, this is the most difficult challenge in the task. I think that doing it without dynamic casting is the hardest part of the exercise. Consider it a stretch goal and come back to it if you have time.

Your Objective

You will implement the Structure class. You can provide and declarations required in task01.h and you may place additional code in task01.cpp.

You will also implement a printElement function overload for Structures themselves. Note: This means that Structures can contain Structures, and the entire construct is hierarchical. This should simply use the print method of the passed in Structure.

Your solution must be able to support adding any element that is assignable, copyable, and has a printElement overload, even if it is not present in the provided code. In other words, you code should again be extensible without modification. It should be open and closed.

You will find tests for this task in the unit01-*.cpp unit tests and corresponding binaries. Additional tests that add new types to the Structure may be used during grading.

Consider: This design hard wires a single printing behavior into the structure. Can we make that behavior itself customizable within this design? If so, how? If not, why not?

Task 2 – Walking the same paths in new ways

In exercise 5, you explored implementing Dijkstra's shortest paths algorithm using inheritance to provide an interface that allows for "programs with holes". Now, you will explore the same problem again, but you are not allowed to use inheritance within your solution. You may feel free to revisit your previous code and tweak it to the new use case. Observe that you must still achieve "programs with holes", and because your solution must be able to work with different types of graphs, this means you will be using polymorphism. Recall that we discussed four forms of polymorphism in class. We saw one in particular that can provide flexible, efficient solutions to this problem. Specifically, approaches based on traits, analogous to type classes, provide a good direction.

Instead of working on a concrete Graph type, your shortest paths algorithm will be able to simply accept different types of graphs as if the implementation were overloaded for them. Nonetheless, you should only implement Dijkstra's algorithm once and reuse it for each graph kind. By defining a type trait that captures the behaviors you require, the algorithm should work transparently. It can also be extended to entirely new types of graphs without modifying any of the code you write in task02.h.

Note that type traits require defining a specialization in order to extend support to a new type of graph. You will need to support the same two types of graphs considered in exercise 5 by defining specializations for them.

Your objective

Define a function called shortestPath in task02.h that returns the list of nodes in the shortest path from a given source node to a given target. When the source and target are the same, the list should contain only one copy of that node itself. When there is no path from the source to the target, the list should be empty. If the shortest path between two nodes contains 128 or more nodes in the graph, then return an empty path instead. Notice that you may not know all of the nodes of the graph in advance. NOTE: In contrast to the function from exercise 5, this one should take three arguments. The first will be the type representing the graph. The second should be the source node. The third should be the target node.

You must use type traits to support a generic interface. You can find the two kinds of graphs from exercise 5 again in Support.h. You should define specializations for these graphs to enable your shortestPath function to work transparently when provided appropriate arguments.

You can work from the provided tests to clarify examples and behavior. You may also be particularly interested in using the weight calculations in unit02.cpp of exercise 5.

Submitting

Create an archive of your solution by changing into the directory containing your project template and running:

tar zcvf e6.tar.gz se-design-ii-template/

You can then upload this archive to CourSys.