Design: Overloading vs. overriding vs. template

Printing shape information requires a function that interacts with various types of shape: circle, polygon, and so on. One way to do this is to have overloaded versions of a function that accepts different type of arguments:

void printShapeInfo(Polygon const &);
void printShapeInfo(Circle const &);

Overloading creates a dependency per version of printShapeInfo to its argument type, but the arguments remain independent from each other. The main drawback is when you add a new shape, for example, ellipse, you also need to add another overload:

void printShapeInfo(Ellipse const &);

And so on for each new type of shape you add.

There are two alternative ways to implement printShapeInfo.

Create a class called Shape. In Shape, declare a pure virtual function description(). Derive Polygon and Circle from it, overriding the inherited member function description().

class Shape {
public:
    virtual std::string description() const =0;
};
class ConvexPolygon : public Shape {
…
string description() const {…}
…
};
class Circle : public Shape {
…
string description() const {…}
…
};
Write a polymorphic printShapeInfo as follows:

std::string printShapeInfo(Shape const & s){
    return s.description();
}

The type of actual argument the parameter s refers to is determined when the call to printShapeInfo takes place. This late binding or dynamic binding eliminate the need to overload printShapeInfo for any new shape along as it derives from shape (or any of its derived classes). The solution ties Circle and Polygon to Shape: they become siblings by deriving from the same base class.

Lastly, you can avoid the overloading hassle by making printShapeInfo a template function:

template <class T>
std::string printShapeInfo(T const & s){
    return s.description();
}

Of course, you must ensure an argument passed to it has the member function description(); an argument without is flagged as compilation error.

Template keeps Polygon, Circle, etc. independent as in the case of overloading.

Delegation from ConvexPolygon to Vector

In the convex polygon problem, we are asked to compute the perimeter of a polygon. We have two obvious options.

Option 1: Perimeter of a convex polygon as a C function 

A convex polygon is an argument passed to this function, which calls the convex polygon’s member function vertex(int) to get vertices to compute distance. The vertex, in turn, is a Vector. So the perimeter function computes distance by getting the components of the two vectors, and then does the square root of sums of square of difference in corresponding components. While all this is going on, perimeter needs to check that the two vectors are of the same dimension.

The perimeter function we just described is busy, nosy, and doing all the work.

Option 2: Perimeter of a convex polygon as a member function 

We can do better. With classes ConvexPolygon and Vector, what perimeter needs to do has been done to a large degree. So, give the perimeter function to Polygon to have direct accesses to the vertices. Have the vector representing two adjacent vertices (i.e., the difference of the two vectors representing the adjacent vertices) compute its own length, checking dimensionality, etc. So, in computing perimeter, ConvexPolygon delegates much of the computation to Vector:

 

The reason that ConvexPolygon is able to delegate computing work to Vector is partly because Vector encapsulates the data and operations Polygon needs. In this case, the operations include Vector's overloaded operator - and the length function; see lines 22 and 23 above. Thus, encapsulation is a foundation for delegation: think about representing a vector with array on numbers and functions all scattered around; it would have been impossible for ConvexPolygon to delegate the computation. 

This delegation is one-way collaboration because Vector does not delegate computing tasks to ConvexPolygon. In contrast, collaboration is two-way or more; more on this later.

Object Design in STL

The C++ standard template library (STL) is loaded with classes and functions that implement commonly used data structures (or containers) and algorithms. Among the former are vector, list, map, set, etc.; among the latter are functions for sorting, searching, finding minimum and maximum elements, etc. The usefulness of them are beyond doubt, as they reflect an old adage by Niklaus Wirth:

Algorithms + Data structures = Programs

The STL makes use of the C++ template construct. The containers are generic in the sense that they work with any type. Thus, 

    int a[] = {-3, 9, 3, 0, 5, -7, 3, 6, -6, 1};
    std::vector<int> v(a,a+10);
    double b[] = {-3.1, 9.2, 3.0, 0, 5.1, -7.3, 3.3, 6.5, -6.0, 1.1};
    std::vector<double> w(b,b+10);

puts ten integers into the vector v and ten doubles into the vector w. 

The algorithms in STL that work with the containers are also type generic, but with two additional constraints. 

First, the data type being processed by the algorithms must support the operation needed. For example, for a sorting algorithm to sort objects stored in a vector, the object type must support various comparison operators (e.g., >, >=, <, and <=).  

Second, each algorithm can only work with containers that support the required way to access data stored inside the containers. For example, sort works with vector but not list because it requires random access to data in the container. Access to data inside a container is provided through an iterator. For example,

    LONGS_EQUAL(-7, *std::find(v.begin(), v.end(), -7));
    CHECK(v.end() == std::find(v.begin(), v.end(), 8));

The find function accepts two iterators and the value it is looking for. The iterators, which mark the range of data inside the vector to look for the given value, are created through v.begin() and v.end(), where v is the vector of ten integers defined previously. The function find works with list as well, as follows:

    int a[] = {-3, 9, 3, 0, 5, -7, 3, 6, -6, 1};
    std::list<int> v(a,a+10);
    LONGS_EQUAL(-7, *std::find(v.begin(), v.end(), -7));
    CHECK(v.end() == std::find(v.begin(), v.end(), 8));

Impressive, isn't it? What makes this possible, in addition to the C++ template construct, is the Dependency Inversion Principle. Algorithms are made to work with iterators instead of containers, so they do not depend on the containers. On the other hand, containers are responsible for creating iterators for accessing the objects stored in them. In other words, both the algorithms and the containers depend on the iterators. Diagrammatically, the dependency relationships change as follows:

 Here's the take-away. 

• Look first in STL for data structures and algorithms you need.
• If you must code up an algorithm, make it work with existing STL containers through iterators.
• If you must code up a container, make it work with existing STL algorithms by having it create iterators for accessing data. 

© Y C Cheng, 2013, 2014. All rights reserved.

Polymorphism

Problem. A program is needed to print the properties of a number of shapes (e.g., Polygon, Circle, etc.) from an input file. The information includes
-- descriptive information (name of the shape, vertices in polygon, center and radius in circle)
-- area, and
-- perimeter.

Following the TDD convention of writing tests first, the following tests are written first:

C++ is strongly typed. Let's call the function printProperties and have it return a string of the properties given a shape object. We must still give the formal parameter of printProperties a type. So we can rephrase our problem as: 

• How to make printProperties accept both Polygon and Circle? Or, 
• How to treat Polygon and Circle as the same type so far as the required member functions are concerned?

C++ provides a way for you to do this. The basic idea is to create an interface between the function printProperties and the shapes that it will potentially accept.

1. Declare a class called Shape which has the required member function declared as virtual. Shape will be the interface that printProperties works with.

The declaration of each member function of Shape begins with the keyword "virtual" to indicate that it can be overridden by a derived class. Also, each member function declaration ends with " = 0" to indicate the the member function is not implemented in Shape. That is, Shape won't ever have an instance because these member functions are not implemented. Combining the meanings of both, Shape is an interface between the function printProperties and the classes Polygon, Circle, etc. In C++, Shape is called an abstract class.

2. Derive Polygon and Circle from shape.

We already have the Polygon class, so all we need to do to make it inherit or derive from Shape. Line 6 reflects this change. The inherited member functions are grouped in a newly added "public:" section (lines 7 - 10). Note that the member functions still begin with virtual (though this is optional) but the trailing " = 0" are now removed. The latter indicates that Polygon must provide the implementation of the three inherited member functions.

3. Use call by reference or call by value-pointer in properties. In the case of call by reference:

 

Doing the same for the class Circle, we obtain an output like this:

How it works

The fact that printProperties work with Polygon and Circle are the result of satisfying three conditions as explained above. The binding of a member function name (e.g., s.area()) with an implementation (e.g., Polygon::area() or Circle::area()) happens at execution time. This form of binding is called late binding or dynamic binding in contrast to static binding which takes place during compilation.

Late binding in C++ works approximately like this.

During compilation, the formal parameter s of printProperties is a reference to the type Shape. The three member functions called through s, including description(), area(), and perimeter(), are declared virtual. C++ compiler takes this as a request to delay binding the implementation until execution time.

During execution time, when the call

    Polygon p=createRegularPolygon(3);
    std::cout << printProperties(p); 
is executed, C++ looks up the implementation for the three member functions though the object p, which is passed by reference.

Late binding incurs an overhead in taking an extra step to look up the implementation of the member function. If you are using an OO language, you should assume that this run-time overhead can be ignored. 

The printProperties function is able to work with Polygon, Circle, and any other shape that derives from Shape. This achieves polymorphism, a corner stone feature of object-oriented languages. The design satisfies the Open/closed principle: 

"software entities (classes, modules, functions, etc.) should be open for extension, but closed for modification"

Shape is open to extension since a new subclass (e.g., Ellipse) can be added without affecting the existing subclasses (e.g., Polygon and Circle) and the function printProperties. That is, Polygon, Circle, and  printProperties are closed for modification. 

Code can be found here.


© Y C Cheng, 2013, 2014. All rights reserved.

Convex polygon

Problem: A convex polygon in the plane is a simple polygon with the property that the line segment determined by any of its two vertices falls entirely within it. Here are some examples of the simplest convex polygons: a triangle, a trapezoid, and a pentagon.

Write a program to compute the perimeter and the area of a convex polygon whose vertices are specified in a file. In so doing, make use of the class Vector we developed.

Step U. Understanding the problem.

The problem calls for the construction of convex polygon and the computation of perimeter and area. It requires that we make use of the class Vector we developed earlier. Precisely, the vertices of the polygon are points in the plane, which are readily represented as 2-d vectors. Immediately, we see that some more functions or member function of the vector are needed. For example, the length of a side is the length of the difference of two vectors representing its two end points.

In computing the perimeter, it is important to note that the vertices of the convex polygon are traversed in the right order:

The perimeter is correctly computed for the rectangle (a convex quadrilateral) on the left by traversing the vertices in the order of A, B, C, D and A. However, the polygon on the right, which is neither convex nor simple, has a longer perimeter than the rectangle. 

Step D. Devising a plan.

Here are the tasks.

T1. Create a convex polygon given a list of vertices, assuming its vertices are ordered correctly.

T2. Create a convex polygon given a list of vertices, assuming its vertices may not be ordered correctly.

T3. Compute the perimeter. (Look here for a discussion of delegation)

T4. Compute the area.

T5. Write the main to interact with user.

Task T1 is a simplified version of Task T2. We could have listed Task T2 only, but that seems more difficult. In particular, if not already correctly ordered, how do we arrange the vertices in a correct order? Listing T1 as a task helps us to concentrate on the design of the object representation of a convex polygon. Furthermore, it can be easily seen that when we can do T1, T2 can be accomplished by finding some way to arrange the vertices. 

Note that although I have omitted the unit tests as specific tasks, it should always be remembered that they are part of a task. In fact, be reminded that unit tests should be the first thing you do in carrying out a task.

The Task T4, computation of area, is not obvious. We know how to do this for the triangle: for example, assuming that the three sides are of lengths a, b, and c, the area of the triangle can be computed with the Heron’s formula by

where

 

With this, the area can be achieved by decomposing the polygon into a number of triangles, for example:

With this we add the following task:

T6. Compute the area enclosed by three vectors.

Note that the task list does not impose an order of the task execution. Therefore you don’t have to rearrange the task numbers.

Step C. Carrying out the plan.

Let us look at the implementation of T2 in some detail. One way to make sure that the vertices of a polygon are ordered correctly is to sort them the around the centroid. To do this, first, find the centroid. Let V1, V2, ...Vn be the vertices of a convex polygon. The centroid O is (V1 + V2 + ... + Vn)/n. Then, locate the vertex with the largest x-coordinate value. When there are multiple vertices tie with the largest x-coordinate value, break the tie by finding the one with the largest y-coordinate. Call this vertex V, and define the reference vector R as the vector V-O. In the pentagon below, the vertex A is the largest X-coordinate value. 

With centroid O and the reference vector R=V-O determined, the angle a vertex U forms with the reference vector R around the centroid O is




since the range of arc cosine in degrees is [0,180] rather than [0,360], we shall take angle to be if the cross product vector of R, U-O is pointing out, and to be 360- if the the cross product vector is pointing in. Since we are dealing with vectors in the plane, the cross product of [u1,v1] and [u2,v2] is simply (u1*v2-u2*v1)[0,0,1]. 
  
Sorting the vertices of the polygon by the angles they form with the reference vector around the centroid, we ensure that the vertices are ordered correctly for the computation of perimeter and area.

The following is an example.

The polygon (a regular pentagon) has the vertices A,B,C,D, and E. O is the computed centroid. R = A-O is the reference vector. The angles the vertices form with the reference vector R around the centroid O are computed as follows:








Thus, even if the constructor of Polygon is given a list of vertices in an arbitrary order, we can make sure that they are brought to a correct order by sorting them around the centroid with respect to the reference vector. In the example above, the vertices are ordered counter-clockwise.

As can be seen, the need to sort vertices requires support from many places: from the Vector class, we need to add an overloading subtraction operator - for subtracting vectors, a  function to compute the angle between two vectors, a function to calculate the length of a vector, a function to decide if the cross product vector of two given vectors is pointing out or pointing in, and so on. Also, we need a function to sort the vertices as defined above. This can be done with a function from the standard template library called std::sort.  

If you check the documentation for std::sort, you will find that the sort function works with array (as well as other containers in the standard template library, but we won't get into that here.) However, it requires you to specify how you compare two objects stored in the array to be sorted. This can be done with the a C-style function or a class object with a member function overloading the function call operator (). For more details, check it out on std::sort.

In the example above, we have

Vector vs[5] = {B,D,C,E,A}; 
Polygon p(vs,5);

Note how the vertices of the polygon p are initially incorrectly ordered (one of the correct orderings would be A,B,C,D, and E). 

In order to sort the vertices, we need to supply a comparator to be used by std::sort. In our case, since the comparator needs to remember the centroid and the reference vector, we will create a class comparator called angleLT (which stands for angle less than) as follows:

to sort the vertices of a polygon P, we do

std::sort(vs,vs+5,angleLT(p.centroid(),p.refVector()));

where Polygon::centroid() and Polygon::refVector() are member functions to compute the centroid and the reference vector, respectively.

Here is the working program including unit tests. The production program is left to you as an exercise.

Step L. Looking back.

In solving the problem of computing the area of a convex polygon, we were able to reuse and make enhancements to the class Vector. As can be seen, the existence of the class Vector makes easy the representation of polygon and the computations of perimeter and area. This is what we normally expect from an object-oriented language like C++: to  construct multiple levels of abstraction so that the problem on hand comes closer to its solution. To see the benefit of this, imagine if you are asked to program the solution to this problem in C. You'll be dealing with lots arrays of doubles at different levels of abstraction. The arrays all look homogeneous in not having a clearly identifiable description  and it is your task to remember their different levels of abstraction. Very taxing indeed.

In looking back, we see that the unit tests are lumped together, and there are more than 600 lines of code of them. It is highly recommended that they be restructured into several files, one file for the unit tests for each of the important classes. This is left as an exercise.    

© Y C Cheng, 2013, 2014. All rights reserved.

Enters matrix

Enters matrix

Problem: In linear algebra, a linear transform is a mapping of an m-dimensional vector into an n-dimensional vector. Familiar examples of linear transformations include rotation and scaling of a vector in the plane (a mapping from a 2-dimension vector to a 2-dimensional vector), projection of a 3-dimensional vector into the plane (a mapping from a 3-dimension vector to a 2-dimensional vector), and so on.

Linear transformation for n-dimensional vectors into m-dimensional vectors is represented by a matrix of m-rows and n columns, or an m x n matrix. Here are some examples from Wikipedia; look under the heading “Linear transformations”.

Let M be an mxn matrix and V be an n-dimensional vector. The m-dimensional vector U = {u_1, u_2,…, u_m} obtained by applying M to V can be calculated by multiplying the matrix M and the vector V:

U = MV,

Where U_i = M_i  ·  V, M_i is the vector of the i-th row of matrix M and  · is the inner product operator, i = 1, …, m.

For example,

A program is needed to compute the vector U, the linear transformation of a given vector V and a matrix M. Specifically, prompt the user to input the name of a file that contain a matrix with the following format:

m n

elements of row 1

…

elements of row m

For the matrix above, the input file looks like this:

2 3

1 2 3

4 5 6

Then, prompt the user to input a vector V of the following format from the console

n [V_1, V_2, …, V_n].

When this is done, the program shall compute the vector U when it is defined, or displays an error message when it is not defined. Prompt the user whether to continue or stop.

In addition to the functional requirements above, the program must meet the constraint of using class, functions, and their tests from the project Inner Product project.

Step U. Understanding the problem.

Functionally, the program is similar to the inner product computation. Of course, we will need a new class to represent matrix, and functions for computing linear transformation and doing file I/O. By now, we have some experiences. We do need to consider the constraints of asking us to use the units from inner product computation.

Step D. Devising a plan.

Here are the tasks.

T1. Prepare two projects, Linear Transformation and it test project.

T2. Write up the Matrix class with the member functions to get row vectors and elements.

T3. Write unit tests for Matrix.

T4. Write file I/O for Matrix.

T5. Write tests for file I/O for Matrix.

T6. Write main function.

Step C. Carrying out the plan.

Let’s start with T1. While the normal way to reuse artifacts from the inner product project is to create a library and use it from the current projects, for simplicity, we will just copy the source files from the inner project into the linear transformation projects and it test projects.

The tasks T2 to T5 should pose little challenge now, we will leave it to you as an exercise to complete them. As before, I strongly encourage you to write up a unit test before you do the member function or function. This has the effect of keeping the class and functions small. However, beware of the memory management issue. Since memory from heap will be used, rather than accepting the C++ defaults, you should write the copy constructor, the destructor, and the assignment operator.

Step L. Looking back.

We see that due to the separation of production and test projects, we can now move at a steady pace by growing the code for matrix piecemeal, all the while insisting that all unit tests pass.

Arguably, the present problem is no less simple than the problem of computing inner products for two vectors. We are able to handle it as a single problem, thanks to our experience from solving the inner product problem. Our capability to handle problem grows. 


© Y C Cheng, 2013, 2014. All rights reserved.