Exercise 5: Basic Inheritance

This exercise will help you practice and demonstrate your ability to use inheritance within basic C++ tasks. You will solve 3 tasks, each one demonstrating one or more facets of understanding why and how to use inheritance effectively. Some tasks will have multiple parts. Some tasks will be easy and some may be hard. Note that these tasks are not focused on syntax but rather on simple problem solving using inheritance.

Once again, there are rules.

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

Note also that some tasks will be graded qualitatively. For those tasks, producing functioning code may not suffice. Instead, you must also show good judgement and design in your code in order to recieve full credit.

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 – To interpret the open and closedness of things

Recall from class that good software aims to be both "open" and "closed". It is open in the sense that it is possible to add new behaviors to the code. It is closed in the sense that its interface is stable so that it can be used by other code without increasing the risk of change. Another way of looking at this is that adding new behaviors should not require existing code to be modified. Classically, this is called the open/closed principle. In class we discussed how this this is also reflected in inversion of control and seen in template based APIs like those in <algorithm>. The benefit of writing code that adheres to these principles is that it can be written once in a generic fashion and used repeatedly.

In this task, you will extend the behavior of an existing system (demonstrating openness) without needing to modify any of the existing features of the system (demonstrating closedness). You will approach this from the perspective of a developer brought into an existing project that cannot be modified and faced with providing new features.

This requires considering an existing system. Brace yourself and prepare to dive in.

You have been provided with source code for a simple interpreter. It works by first using a Translator to translate a "source code" string into a Program. A Program is nothing more than a list of Operations. An Interpreter can then evaluate a Program. Given a sequence of arithmetic operations, the interpreter can perform those operations. In order to do this, it uses a simple stack machine. An operation, such as addition, can (1) consume the top values of the stack, (2) perform some computation, and (3) push new values onto the stack. Thus, given an operation like add X Y, the operation can (i) pop Y off the stack, (ii) pop X off the stack, (iii) add the two values together, and then (iv) push the result back onto the stack.

You can construct the default Translator using the buildDefaultTranslator function. Several operations are supported by default. You can see their implementations within T1Interpreter.cpp if you wish. This includes operations like:

• PUSH, which pushes a constant value to the stack,
• POP, which removes the top value from the stack,
• DUPLICATE, which pushes a copy of the top value of the stack,
• ADD, which adds the top two values of the stack,
• NEGATE, which replaces the top value X with -X,
• SUBTRACT, which removes the top two values from the stack and subtracts the top from the value directly below it,
• PRINT, which prints the top value of the stack, and
• SAVE, which preserves the current top value of the stack as the result over the overall evaluation.

Notice that the behavior of Interpreter is very generic. It does not care what the Operations in the program are. Every Operation must have two methods: evaluate and getSpecification. By supporting these methods and extending Operation, the specific types of operations do not need to be known in order to execute. The evaluate method performs an action on the ProgramState, and getSpecification yields an OperationSpecification that contains the number of operands for an operation and the overall change in the stack size after executing the operation. For example, ADD has two operands and has a relative stack difference of -1 because it removes its two operands and then pushes a single result of the addition.

Look at the implementation of evaluate for Operation in Support.h. Notice that it enforces the checking for the correct number of arguments before invoking the overridden behavior. This guaranteed enforcement of invariants is one of the advantages of the non-virtual interface idiom. In many languages, this is referred to as a "template method" pattern. Checking of preconditions and postconditions in code that cannot be overridden allows extending the behavior of the system with confidence that invariants are not violated. Users of the class are unable to invoke the extended behavior without the class invariants being checked. It also avoids obfuscating the business logic with checking of extra correctness conditions.

The Translator determines which Operations are created for the different "spellings" seen within source code. It maps the spellings of operations to an OperationFactory that can create new instances of an instruction. Notice that the Translator is also generic. As long as a Factory can create Operations, the Translator does not care what the operations do. You can register new Factories for spellings to add new behaviors to the language, enriching the abilities of the language.

This is the system in which you will be working. In particular, you want to understand Operations and OperationFactorys.

Your objective

You will enrich the language with new operations and new computational powers. Specifically, you will add new operations to the language. Note that you do not need to change any of the existing code in order to achieve your objective. In fact, you do not need to understand how existing operations are implemented. The system is both open and closed.

You will write a new function buildEnrichedTranslator returning a Translator. This Translator will support several additional Operations. The Operations you need to add are:

• MULTIPLY removes the top two values from the stack and pushes their product.
• DIVIDE removes the top two values from the stack and pushes the value beneath the top divided by the top. Division is truncating integer division.
• GROW is special because it modifies its behavior each time that it executes. The first time that it executes, it pushes 1 to the stack. The second time it pushes 2. The third time it pushes 3, and so on.

In any case where the arguments are not available or the semantics of evaluation do not make sense, the evaluate method should return Outcome::FAILURE.

You will write a new function buildFancyTranslator returning a Translator. This Translator will support the normal default Operations and none of the new ones you wrote, but the PRINT Operation should print out the top value of the stack surrounded by >>> <<<. For instance, if the top value of the stack is 3, then >>>3<<< followed by a newline will be printed.

Provided tests for the task can be found in test/unit01.cpp and compile to bin/unit01. You can see examples of the translation of source code into programs and the interpretation of programs within these tests.

Task 2 – The space between the gaps OR Making use of negative space

Task 1 looked at extending the behavior of an existing system already designed for it. Task 2 focuses on the dual perspective of designing a system that is meant to be extended. This aspect of inversion of control is the same as the idea of writing programs with holes that are meant to be filled in by another part of the system or perhaps entirely different developers later on.

In this task, you will write a program using a specification of what the holes to be filled in can be. It will be simpler than the more extensible design that you used in Task 1. In fact, you should find it to feel no different than normal programming. The power comes from abstracting the solution and realizing that the "hole" to be filled in by a user broadens the applicability of the solution. You should also notice certain limitations or oddities that arise when using inheritance to achieve this objective. Those will be revisited in the next exercise on design.

In this task, you will simply implement Dijkstra's algorithm for finding the shortest path in a weighted directed graph between a source and a target node. Recall that a weighted directed graph consists of nodes and edges where an edge has a weight that represents the cost of moving from the source of the edge to the target of the edge. The algorithm is frequently taught in second year classes and finds the lowest cost route from one node to another. Feel free to brush up on it if you are uncertain. The Wikipedia link above provides a clear explanation and pseudocode that can be followed directly.

Instead of working on a concrete Graph type, you will use a Node interface. You can see the definition of this interface in Support.h. Observe that the only method of interest in this interface is getSuccessors and its overridable implementation. This method returns a list of outgoing edges from a node along with the associated costs of traversing those edges. Your task solution should work for any graph that implements this interface for its nodes.

Your objective

task02.h defines a function called shortestPath 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. Notice that you may not know all of the nodes of the graph in advance.

You must implement this function within task02.cpp. The efficiency of the data structures you use does not matter. The overall algorithmic complexity does not matter for this task as long as the running time is reasonable. You may assume that node identity can be uniquely determined by address.

Provided tests for the task can be found in test/unit02.cpp and compile to bin/unit02. Look at the use cases of the algorithm in test/unit02.cpp. Notice that they are not all traditional graphs! Using shortest paths in context allows solving related problems with a single implementation. In particular, the second set of tests is able to find a sequence of "hops" among anagrams (or minimal edits) in a dictionary to turn one word into another while keeping individual changes between words small. Consider what downsides may exist with respect to the design.

Task 3 – Keeping your composure and tidying up the garden

This task specifically will be graded on both design and functionality.

You are in charge of a Garden full of calming flowers. The Garden class has been provided to you in Garden.h inside the solution library, but the Garden is incomplete because the Flowers have not been provided to you. There are many types of Flowers that should exist in the Garden, each interacting with it in a different way. You must flesh out the implementation of the different types of Flowers and complete the functions that can create them so that the Garden may be complete. Then you can finally relax in the Garden.

Every Flower has several properties and behaviors. Yes, even flowers exhibit behavior. Some of these are determined by the type of the Flower, while others are specific to each individual Flower. In particular, each flower has the properties:

• location – The location of a flower is simply where it resides within the Garden. This is represented by the Location object and is known upon creating an instance of any specific Flower. Conceptually, locations comprise a row and a column, oriented such that positive rows extend up the X,Y plane and positive columns extend to the right.
• color – The color of a flower is the primary blossom color of the flower. It is represented by the Color enum provided to you. The color can be determined by the specific type of Flower, but for other Flowers it can also be something that is affected by the environment or the passage of time.
• root growth – The root growth is a number that captures the spread of a Flower's roots into the soil. It is captured in the RootGrowth type. The units do not matter. Root growth always starts at 0.
• height – The height of a flower. The units do not matter. The height always starts at 0.
• bloom – The overall size of the bloom of the flower. The units do not matter. The bloom always starts at 0.

Each Flower also has a few different behaviors:

• void grow(const Garden&) is a method that allows a Flower to grow. Different Flowers may grow in different ways. For instance, a sunflower may grow primarily in height and bloom if the sun is not blocked out around it.
• std::unique_ptr<Flower> spread(const Garden&) is a method that allows a Flower to create a new instance of the same kind of Flower in an adjacent location. Again, different Flowers will spread in different ways. If a Flower cannot spread, an empty unique_ptr is returned.

You must be able to support at least three different kinds of Flowers.

• Sunflowers
  • grow – A sunflower is a light dependent grower. It grows when there is sufficient sunlight around it. When a sunflower is surrounded by fewer than 3 flowers taller than itself, the sunflower will grow by incrementing its height by 2, its bloom by 1, and its roots by 1.
  • spread – A sunflower is a vertical spreader. It will create a neighboring sunflower with a Location in a row one greater than its own if the space is unoccupied. Otherwise it will create a neighbor with a row one less than its own if the space is unoccupied. Otherwise, it cannot spread.
• Mycoheterotrophs
  • grow – A mycoheterotroph is a root dependent grower. It grows when there is sufficient room within the roots around it. When the total root growth of surrounding flowers is less than or equal to twice its own, a mycoheterotroph will grow by incrementing its roots by 2, setting its height to 1, and setting its bloom to 1.
  • spread – A mycoheterotroph is a clockwise spreader. It will create a neighboring mycoheterotroph in the first unoccupied Location found starting from the row immediately above the this Flower and searching in a clockwise fashion.
• Rafflesia arnoldii (corpse lily)
  • grow – Rafflesia arnoldii is a parasitic rootless, stemless plant with a massive bloom. It grows when it can extract resources from the plants around it. When the total height and root growth of surrounding flowers is greater than or equal to its bloom, a corpse lily will grow by incrementing its bloom by 2 and ignoring all other attributes.
  • spread – The corpse lily is a horizontal spreader. It will create a neighboring corpse lily with a Location in a column one greater than its own if the space is unoccupied. Otherwise it will create a neighbor with a column one less than its own if the space is unoccupied. Otherwise, it cannot spread.

Flower should also have basic accessors for its properties.

Your objective

task3.h declares three functions for creating sunflowers, mycoheterotrophs, and corpse lilies. You must implement these three functions in task03.cpp. In order to do so, you must also implement the Flower class and any additional support classes that you want in the process to create at least the three kinds of Flowers above. Support.h contains types for Location, Color, RootGrowth, Height, and Bloom.

The Garden class is provided to you within the solutions library, but you may not modify it. You may use it to find neighboring plants Provided tests for the task can be found in test/unit03.cpp and compile to bin/unit03. The efficiency of your solution will not specifically be graded, but your design matters.

Submitting

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

tar zcvf e5.tar.gz se-inheritance-template/

You can then upload this archive to CourSys.