CSE 201 - Tutorial 6 - Enumerations, objects by reference, and template functions

Setting up the tutorial.

1. Download the handin of the tutorial CSE201-td6-1-handin.zip.
2. Extract the handin of the tutorial. This will create the folder CSE201-td6-1-handin.
3. Open QT Creator, then go on the menu “File”, then select “Open File or Project…”. Navigate to the CSE201-td6-1-handin folder and select the file td6.pro.

For this tutorial you will only edit the file td6.cpp and td6.hpp.

Evaluation.

You will be evaluated on all the exercises for a total of 100 points. The exercises give the following amount of points:

--------------------------------------------------------------------------------
Scores summary:
--------------------------------------------------------------------------------
1 status_target: 10
2 halve_distance: 10
3 count_point: 10
4 count_coordinate_instances: 10
5 get_distance_template: 20
6 list_templates: 25
7 list_copy: 15

Total: 100
--------------------------------------------------------------------------------

Rules for the evaluation:

• A program that does not compile will receive 0 points: this means that your program cannot contain syntax errors (e.g., forgetting the ; sign after a statement) and typing errors (e.g., assigning an array variable to an integer variable);
• Each program will be evaluated running on a set of different inputs. You will receive the points for an exercise if your implementation behaves correctly an all the test cases.

Run the automatic grader on your computer first and submit your solution for each exercise as soon as you have one, so we can track the class progress.

Working on the tutorial

This tutorial will require you to define some new types and functions. The test cases in the automatic grader, however, need the declaration and the definition of these classes to compile correctly. So, initially the automatic grader will not try to compile and execute the test cases for the exercises. For example, you will see an output like this for the first test case coordinates_overload_arithmetic:

START TEST - status_target


END TEST - status_target: [FAILURE] (0 correct test cases out of 0)
--------------------------------------------------------------------------------

You see the 0 correct test cases out of 0 in the output and no test cases because the test needs your implementation of the first exercise to work.

How can you enable the compilation of the test case?

In the td06.hpp there are some define preprocessor directives, one for each exercise:

#define EXERCISE_1 0
#define EXERCISE_2 0
#define EXERCISE_3 0
#define EXERCISE_4 0
#define EXERCISE_5 0
#define EXERCISE_6 0
#define EXERCISE_7 0

To enable the automatic grader for one exercise you need to change the value from 0 to 1. For example, you can change the line from:

#define EXERCISE_1 0

to

#define EXERCISE_1 1

to try to compile the automatic grader and run the test cases for the 1st exercise.

You can work as follows to minimize your development time:

• Start from the first exercise, defining types and function declarations. You can leave the body of the functions empty at this stage.

• Then you should try to compile your code to fix your errors - do not proceed if your code does not compile.

• You can to set the EXERCISE_1 define to 1 as soon as your code compiles (without the function implementation): this should be sufficient for the automatic grader to compile. You will most likely find some compilation error (e.g., due to missing functions, wrong names, wrong type of parameters). Pay attention to the earliest compilation message and use it to fix your implementation.

• Work in order on the exercises and enable the test cases for one exercise only when you completed the previous ones (all the exercises depend on the definitions you need to provide in the previous ones).

WARNING: the online automatic grader will also not give you any detailed information about a test cases if you do not enable the automatic grader for that exercise. This is because the automatic grader will not execute any specific test case (and so there is no first test case that fails). The automatic grader will still report (correctly) that your implementation failed and the detailed output log will still be valuable (e.g., it contains all the compiler output).

Submitting your Work

• The deadline for submitting the exercise is next Sunday, November 13th, at 23:59 Paris time.

• IMPORTANT: your final grade is the one that the server computes (and not what you see on your machine).

1. Add a status to the Target class

The Target class is declared in the td6.hpp file (in the following code we show only the function prototypes and data members that you need to be aware of, while the full declaration is in the td6.hpp header):

class Target {
public:
  Target(Coordinate position_other, double radius);
  Target();
  virtual void toggle_status();
}

In the first exercise:

1. Use an enum to declare an new enumeration type called TargetStatus with values destroyable, unbreakable, and hidden.

   NOTE Use exactly the above names for the enumeration types and values, otherwise your code will not compile.

   The status determines if the Target can be destroyed or not when hit by a projectile, or if the target is hidden.

2. Add a private data member of type TargetStatus to the class Target and declare and implement the following functions to just get and set the status of the target:

   TargetStatus get_status();
   void set_status(TargetStatus status);

3. Implement the body of the following function that changes the status of the target every time the function is called:

   void Target::toggle_status();

   The status should be updated as follows:

   • if the status is destroyable, then the status is updated to unbreakable.

   • if the status is unbreakable, then the status is updated to hidden.

   • if the status is hidden, then the status is updated to be destroyable again.

   Initially the status is destroyable.

2. Find the midpoint of a segment

Consider the usual Coordinate class (here we show only a subset of the class defined in common.hpp):

class Coordinate {
public:
  Coordinate(double x_other, double y_other);
  Coordinate();
  double get_x() const;
  double get_y() const;
  void set_x(const double x);
  void set_y(const double y);
  double get_distance(Coordinate other);
private:
  double x;
  double y;
};

and the function:

Coordinate halve_distance(const Coordinate &c1, const Coordinate &c2);

The function is already implemented in the td6.cpp file. However, the function does not compile because the implementation tries to changes the variable c1, which is marked as const. You will see a compilation error similar to the following ones (the exact error may change depending on your specific compiler):

../td6.cpp:32:3: error: 'this' argument to member function 'set_x' has type 'const Coordinate', but function is not marked const
c1.set_x((c1.get_x() + c2.get_x()) / 2);

../../CSE201-td6-1-handin/common.hpp:16:8: note: 'set_x' declared here
  void set_x(const double x);
       ^
../td6.cpp:33:3: error: 'this' argument to member function 'set_y' has type 'const Coordinate', but function is not marked const
  c1.set_y((c1.get_y() + c2.get_y()) / 2);
  ^~
../../CSE201-td6-1-handin/common.hpp:17:8: note: 'set_y' declared here
  void set_y(const double y);

Modify the implementation of the function halve_distance to fix the bug (hint: the fix does not consist of removing the const keyword but to change the function body).

3. Count the half segments

Implement the function:

int count_half_segments(Coordinate start, Coordinate end, double min_distance);

that counts how many times we can recursively divide the segments connecting the points start and end, represented with two Coordinate objects, in two equal segments of the same length and with a length of at least min_distance.

The mathematical formulation of the function count_half_segments would be (we use \(count\) instead of count_half_segments here): \[ count(p1, p2) = \begin{cases} 1 + count(p1, m) + count(m, p2) & \text{ if } d(p1,m) \ge k\\ 0 & \text{ otherwise}\\ \end{cases} \]

where \(p1,p2\) are two points (i.e., two objects of type Coordinate), \(m\) is the point at the same distance between \(p1\) and \(p2\) (i.e., the point you would get from the function halve_distance), d(p1,m) computes the distance between p1 and m (use the get_distance function of a Coordinate object), and k is the minimum length of the segment.

The function checks if the length of the segment between p1 and m is at least k (meaning that you can have a segment from p1 to m of at least length k, and the same for the segment from m to p2). If that is the case, the function recursively performs the same operations for the segments p1 to m and m to p2, and add 1 to the result. In the other case, the function just returns 0 (i.e., the segment connecting p1 and m is not long enough).

For example, let \(k = 1\): \[ count(Coordinate(0,0),Coordinate(0,0)) = 0 \\ count(Coordinate(0,0),Coordinate(1,1)) = 0 \\ count(Coordinate(0,0),Coordinate(2,0)) = 1 \\ count(Coordinate(0,0),Coordinate(4,0)) = 3 \]

For count(Coordinate(0,0),Coordinate(4,0)), the function would:

• compute the middle point, which is (0,2)
• compute the distance between (0,0) and (0,2), which is 2. Since \(2 \ge k = 1\), the function would recursively compute count(Coordinate(0,0),Coordinate(0,1)) and count(Coordinate(0,1),Coordinate(2,0)), adding the results from these two functions and 1.
• the computation of count(Coordinate(0,0),Coordinate(0,1)) would return 0, since the distance between (0,0) and the middle point is less than k. Similarly, the same happens for count(Coordinate(0,1),Coordinate(2,0)).

HINT: Follow the definition of the function count to implement count_half_segments using recursion.

4. Limit the copies of coordinates

The function count_half_segments you defined above had the signature:

int count_half_segments(Coordinate start, Coordinate end, double min_distance);

meaning that the function arguments are passed by value. Passing the objects start and end by value means that the object passed as argument to the function is copied.

Copying an object may be expensive and difficult, for example if your object contains other objects or instantiated memory on the heap. Note that if you have a pointer as data member in your class the default copy mechanism will copy the pointer value, so you will end up with two different objects pointing to the same area of memory on the heap (can you think why this could be an issue?).

Furthermore, a function like count_half_segments calls itself recursively for an exponential number of times (every time the function calls itself twice). However, inside the function we do not change the value of start and end.

Modify the definition and the declaration of count_half_segments to avoid the explicit copy of the objects (hint: you can use references and the modification of your code should be minimal).

The automatic grader will test your implementation calling the function count_half_segments and counting the number of Coordinate objects that are created by your program. The function that will be used for testing is called count_coordinate_instances and is already defined for you:

int count_coordinate_instances(Coordinate c1, Coordinate c2, double min_distance) {
 int num_instances = Coordinate::get_num_instances();
 count_half_segments(c1,c2,min_distance);
 return Coordinate::get_num_instances() - num_instances;
}

so, the function:

count_coordinate_instances(Coordinate(0,0), Coordinate(0,0), 1)

counts the number of coordinates you create when calling count_half_segments. If you keep the definition that pass the coordinates by value, your function will return 3, while the expected result is 1 (in fact, you still need to create a new coordinate to store the intermediate point).

The output of the test will be similar to:

[FAILURE] count_coordinate_instances(Coordinate(0,0), Coordinate(0,10), 1): got 50 expected 15

The above output means that your function instantiates a new coordinate object for 50 times, instead of 15.

If you are a careful observer you noticed that the count_half_segments function can avoid an exponential number of function calls by exploiting symmetry. This is a great optimization, but it’s not good enough to pass all the test cases.

5. A generic function to compute the distance

The class Coordinate defines a function get_distance to compute the distance between two coordinate objects. However, we do not have such function for computing the distance between two Projectile objects, between two Target objects, or between a Target and a Projectile object.

Define a function template named get_distance that takes as input two objects and returns a double, and that can accept as input objects of type Projectile and/or Target. Note that:

• the template should work when mixing Target and Projectile objects; and

• both the Projectile and Target class define the same get_position method.

NOTE: all the function templates must be defined in the td6.hpp.

6. Generic list operations

Last week you implemented a list to store objects of type Projectile. This week we already provided you the implementation of two list data structures: one list stores objects of type Projectile, called ProjectileList (defined in common.hpp file), and the other list stores objects of type Target, called TargetList (defined in td06.hpp file).

Since we are lazy, we want to implement the copy operation that works for both list types while writing the code for the function onyle once. In this exercise, we will define several function templates to wrap the existing operations on the lists.

We already provided you two function templates for creating a list and appending an element:

template<typename ListType>
void init_list(ListType *&list) {
  list = new ListType();
}

template<typename ListType, typename ElementType>
void append(ListType* list, ElementType element) {
  list->append(element);
}

A detail in the implementation is the use of a reference to a pointer ListType *&list in the init_list function. This means that you can create a new list as follows:

ProjectileList *l;
init_list(l); // after this function l will point to an object of type ProjectileList

Remember that, for the example above, the compiler will automatically create the function:

void init_list(ProjectileList *&list) {
  list = new ProjectileList();
}

Also, note that all the above functions already use the functions from the list classes we already provided you (e.g., append is a function defined in both lists).

Implement the following function templates:

• is_list_empty: the function takes as argument a pointer to a list and returns a boolean that is true if the list is empty.

• remove_from_head: the function takes as input a pointer to a list and a reference to an element in the list. The function removes the head element in the list and assigns it to the second argument. One should be able to use the function as follows:

      Projectile p1, p2, element_from_head;
      ProjectileList *l;
      init_list(l);
      append(l,p1);
      append(l,p2);
      // extract the head element from the list and assign it to element_from_head
      remove_from_head(l, element_from_head); // at this point element_from_head should be equal to p1

  Note that the type of the second element should be a reference. For example, when instantiating the function template for the types ProjectileList and Projectile we would get:

    void remove_from_head(ProjectileList* list, Projectile& p) {
      ...
    }

• remove_from_tail: the function takes as input a pointer to a list and a reference to an element in the list. The function removes the tail element in the list and assigns it to the second argument (similarly to remove_from_head).

NOTE: in the next lecture we will see how we can use templates directly when defining a class. This will saves us a lot of work and to define a new list implementation for every different data type.

7. A generic function to move a list

Implement the template function:

template<typename ListType, typename ElementType>
void move(ListType* source, ListType *&destination, ElementType to_exclude) {
}

that moves all the elements from the list source to the list destination, maintaining their order. The function does not insert in the list destination all the elements that are equal to to_exclude (however these elements are still removed from the source list). Note that the source list will be empty even if it contains the element to_exclude.

Note that you have to explicitly initialize the list destination inside your function.

For example, after executing the code:

ProjectileList *l1, *l2;
Projectile p1(Coordinate(1,1),1,45);
Projectile p2(Coordinate(2,2),1,45);
init_list(l1);
append(l1, p1);
append(l1, p2);
move(l1,l2, Projectile(Coordinate(4,5),1,45));

the list l1 will be empty, while the list l2 will contain the elements (in this order): Projectile(Coordinate(1,1),1,45) and Projectile(Coordinate(2,2),1,45).

Instead, after executing the code:

ProjectileList *l1, *l2;
Projectile p1(Coordinate(1,1),1,45);
Projectile p2(Coordinate(2,2),1,45);
init_list(l1);
append(l1, p1);
append(l1, p2);
move(l1,l2, p1);

l2 will only contain p2 (i.e., Projectile(Coordinate(2,2),1,45).