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.

Inner product, round 4: refactoring into object

One of the benefits of moving from C to C++ is your enhanced capability to describe things in ways that are cognitively less taxing. Entering round 4, the only problem in the backlog is P5:

P5. Representation of vectors: Vector should remember its own dimension; use of vector should follow the convention in mathematics.

So, let's work on P5. To do this we need to use the class construct: C++'s way of letting you wrap scattered things into one cohesive piece. Before that, it is important that we understand what kind of an impact the new representation brings to the working program obtained at the end of round 3. Assuming that we have vector objects instead of array of doubles, which code must be changed?  

I hope you are not surprised by the answer: all. Our program is only about vectors and computing inner product of two vectors, so all code is related to the representation and manipulation of vectors with arrays of doubles. But answering all does not help much. Should you just throw away the code of round 3 and start over from scratch?  Certainly not. The code works, and it has been unit-tested. You need to re-use the code as much as possible. With this in mind, let us begin the next round.

Step U. Understanding the problem.


Let's try to introduce some structure into the problem even if we know all code is potentially subject to change. The structure will allow us to come up with a list of tasks which we can choose to complete with good rationale. Let's draw a figure:

In the figure, a small cloud represents the object we want to introduce to the program to replace a certain existing concept. In the present case, we plan to introduce Vector objects to replace arrays of doubles for representing mathematical vectors. In the diagram, a rectangle represents a function or the unit tests for a function. An arrow from rectangle A to rectangle B means that A uses or depends on B. For example, the function main depends on the function computeInnerProduct because the former calls the latter. In the same manner, an arrow is drawn from rectangle to the small cloud if the former is affected by the introduction of the latter. In short, they are the units that are directly impacted by the introduction of the new class. For example, the function extractVectorFromString is affected by the introduction of vector since it needs to return a vector instead of an array of doubles.

With the figure, we quickly grasp a picture of the impact in replacing arrays of doubles with vector objects. The figure gives a crisp picture of our answer of "all": All units need to change. 

Step D. Devising a plan.

In what order should we go about the changes? Which unit should we start with? In answer these questions, let us remind ourselves that we are always interested in maintaining a working program. Let us apply that to the ordering of changing the units. So we will change one unit at a time. 

The following list of tasks is a plausible decomposition based on the "uses" or "depends" relationship.

T0. Learn class construct, constructors, destructors, and other member functions.
T1. Code up the vector class.
T2. Test vector.
T3. Change the function inner product.
T4. Change the unit test of inner product.
T5. Change extract vector from string.
T6. Change the unit test of extracting vector from string.
T7. Change get vector from user.
T8. Change main.
T9. Test main by running the program.
T10. Clean up in the reverse order of changes. 

A long list, but definitely doable. A note about T10. When making changes, there is a tendency for us programmers to keep the old code, on the ground that the old code might still be useful. My suggestion: Don't. Even if you know you need the old code, there are better ways to do it. We will come back to this later.  


Step C. Carrying out the plan. 

Let's look at T1 and T2 in detail. Further, let's do T2 first:
 TEST (Vector, create)
{
    double a[2]={1,2};
    Vector v(a, 2);

    LONGS_EQUAL(2,v.dim());
    DOUBLES_EQUAL(1,v.component(1),0.001);
    DOUBLES_EQUAL(2,v.component(2),0.001);
} 
Compiling the test project would fail because we have yet to code up the vector class. But the test is a good thing because it tell us what we expect from the class:

• creating a vector
• obtaining its dimension
• obtaining the component by dimension.

Here, we have decided that the new class will be called Vector. Note that we follow the convention of beginning a self-defined class with a capital letter. Moreover, the dimension and component given index will be obtained through the corresponding calls to member functions dim and component.

Let's tackle T1, writing the Vector class. The C++ class construct is a mechanism for you to create an abstraction that involves both data and operations. What are the data and operations we have been using around the concept of vector?

The main function of round 3.

Checking the main program of round 3, we found the following:

• dimension of vectors (line 7)
• pointer to array of doubles (line 8)
• creation of vectors (lines 14 and 15; code not shown)
• deletion of vectors (lines 22 and 23)
• access of vector components (line 7 in computeInnerProduct; not shown here)

Diagrammatically, we have a set of associated data and operations as depicted below:

 Since we are going to share the class Vector between the production project and the test project, we will follow the convention to separate its code in two files: Vector.h and Vector.cpp. Here is the header file:

#ifndef VECTOR_H_INCLUDED
#define VECTOR_H_INCLUDED
class Vector {
public:
    Vector (double a[], int d);
    Vector (Vector const & v);
    int dim() const;
    double component(int i) const;
    ~Vector();
private:
    double * coms;
    int d;
};
#endif // VECTOR_H_INCLUDED

Below "public:" we have five operations: two constructors for creating instances (or objects) of Vector, member functions dim() and component(int) for getting the dimension and component of vector given the dimension, and a special member function called the destructor. These operations are public so that they can be called from outside of the class (e.g., v.component(1) in the test case). 

Below "private:" we have the data that make up the vector: the components and the dimension. They are private so that they direct access of these data members are flagged as compilation errors (e.g., v.dim = 3.)

Diagrammatically, the class Vector is represented as below.

The compartments from top to bottom are name of the class, data members (adorned with '-' for private) and member functions (adorned with '+' for public). As a convention, we won't include the constructors and the destructor, and we don't show the private member functions.  

What's a good order to do T3 and T4? Let's begin with T4. In T4, we redo test computeInnerProduct for vector version; it should pass when T3 is done. By writing tests first, we are actually thinking about what kind of an interface the new method should have. In other words, we are designing the interface of the new function computeInnerProduct:

TEST (computeInnerProduct, vector)
{
    double u[2] ={1,2};
    double v[2] ={1,1};
    vector w(u,2);
    vector x(v,2);

    DOUBLES_EQUAL(3, computeInnerProduct(w,x),0.001);
}

When T4 is done, we have code like this:

double computeInnerProduct (double v1[], double v2[], int d1, int d2) {
...
}

double computeInnerProduct (vector v1, vector v2)
{
    if (v1.dim() != v2.dim())
        throw "Vectors of different dimension!";

    double r=0;
    for (int i=1; i<=v1.dim(); ++i) {
        r += v1.component(i)*v2.component(i);
    }
    return r;
}
 
At this point, we have both the old and new versions of computeInnerProduct. We are going to keep the old version around for a while because we are have yet to change the main function (T8). If the old version is removed, the compilation of both the production project and the test project would certainly fail. The old and new versions can coexist, thanks to the C++ feature of allowing a function name to be overloaded: Two functions can have the same name if their arguments are different in type.

The tasks of T5 and T6 are done in the same way. Note that the use of vector class eliminates the argument int &dim:

  double *  const extractVectorFromString(std::string line, int & dim)

  vector extractVectorFromString(std::string line)
    
The old version needs to pass the dimension back to the main function, but since the return value of the function is taken up by the allocated array, the dimension is made an additional argument and is a call by reference is used. In contrast, the new version now keeps the dimension inside the vector and has a cleaner interface.

T10 is a task of its own because we want to be careful when removing things: One unit at a time. For example, we can begin by removing the old version of computeInnerProduct. The product project should compile and execute correctly, but test project would fail to compile since the some existing tests depend on old computeInnerProduct. These tests are removed.   

Here is the working program.

Step L. Looking back.

Is the program easy to understand? Does it have more "vector-ness" than "array-ness"? Let's look at the code:

The only places we use vectors are:

• creating vectors (lines 12 and 13)
• passing vectors to computeInnerProduct (line 14)

Carefully compare code in the main function with its predecessor: There's no longer "array-ness" in the code, and the use of Vector objects are concise and easy to understand.

You should do the review for the other functions as well to convince yourself of the improvement.

In this round, we have changed the representation of vectors without changing the functionality of the program. The systematic way we did this called refactoring.

Is  the program good enough? I'll leave it to you to figure out and improve with yet another round. It's time to move on.

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