The const Keyword

The const keyword is a type qualifier in C++ that allows us to prevent an object from being modified. As an example, consider the following erroneous definition of strcpy():

void strcpy(char *dst, const char *src) {
  while (*src != '\0') {
    *src = *dst;
    ++src;
    ++dst;
  }
  *src = *dst;
}

In this definition, the assignments are backwards – the code is attempting to modify the source string rather than the destination. However, because the src parameter was declared with type const char *, the compiler will detect this error:

$ g++ --std=c++17 strcpy.cpp
strcpy.cpp:3:10: error: read-only variable is not assignable
    *src = *dst;
    ~~~~ ^
strcpy.cpp:7:8: error: read-only variable is not assignable
  *src = *dst;
  ~~~~ ^
2 errors generated.

A variable declared as const can be initialized, but its value cannot be later modified through an assignment. For a simple type, the const keyword may appear on either side of the type:

const int x = 3;  // initialization is OK
int const y = 4;  // const can go on the right as well
x = y;            // ERROR: attempt to assign to const object

Only types with values may be declared as const. The following types do not have values:

  • References; they alias objects that may have values but do not have values of their own.

  • Arrays; we will see arrays later in the course.

  • Functions; we will see function types later in the course.

References and const

We saw previously that the binding between a reference and the object it aliases is established at initialization, and it cannot be broken as long as the reference exists. Thus, it is not meaningful for a reference itself to be const.

While a reference does not have a value and thus cannot be declared as const itself, it can refer to an object with const type. The const keyword can appear to the left of the & in a reference type, as in const int & – this is read “inside out” as “reference to a constant int”. The object the reference is aliasing is not modifiable through the reference:

int x = 3;
const int &ref1  = x;  // reference to const int
int const &ref2  = x;  // const can go on the right of int as well
ref1 = 4;              // ERROR -- attempt to assign to const object

However, the original object is still modifiable if there is a non-const way to refer to it:

int x = 3;
int &ref1  = x;
const int &ref2 = x;
x = 4;                 // OK -- x not declared as const
ref1 = 5;              // OK -- ref1 a reference to a non-const int
ref2 = -6;             // ERROR -- ref2 a reference to a const int

The example above has three names that refer to the same object. However, the object is only modifiable through the names that do not include the const keyword.

In the two previous examples, we have created reference-to-const aliases for a non-const object. We will see shortly that non-const to const conversions are allowed, but the other direction is prohibited.

Pointers and const

Pointers do have a value, so they can be declared as const. To do so, the const keyword is placed to the right of the *:

int x = 3;
int y = 4;
int * const ptr = &x;
*ptr = -1;             // OK -- ptr is pointing to a non-const int
ptr = &y;              // ERROR -- attempt to assign to const object

Reading the declaration of ptr inside out, we get “ptr is a constant pointer to an int.” Thus, we cannot modify the value of ptr itself. However, since the type that ptr is pointing to (what is to the left of the *) is not const, we can modify the object that ptr is pointing to.

Similar to a reference, we can declare that the object that a pointer is pointing to is const by placing the const keyword to the left of the *:

int x = 3;
int y = 4;
const int * ptr = &x;  // equivalent: int const *ptr = &x;
ptr = &y ;             // OK -- ptr is not const, so we can change its value
*ptr = -1;             // ERROR -- attempt to assign to const object

Finally, we can declare that both the pointer itself and the object it is pointing to are const:

int x = 3;
int y = 4;
const int * const ptr = &x;
ptr = &y ;             // ERROR -- attempt to assign to const object
*ptr = -1;             // ERROR -- attempt to assign to const object

const Conversions

We’ve seen examples above where we’ve constructed references-to-const and pointers-to-const objects from objects that were not declared as const. The general rule for converting between const and non-const is that the conversion must not enable modifications that are prohibited without the conversion.

A const object can appear on the right-hand side of an assignment, since an assignment has value semantics – it copies the value from the right-hand side to the left-hand side object. Thus, it does not permit the const object to be modified:

const int x = 3;
int y = x;         // OK -- copies value from x; does not enable x to be modified

On the other hand, if we initialize a reference-to-non-const with a const object, we would enable the object to be modified through the reference. Thus, such a conversion is prohibited:

const int x = 3;
int &ref = x;      // ERROR -- enables const object to be modified through ref
ref = 4;           // would modify the x object if the above were allowed

The same goes for placing the address of a const object in a pointer-to-non-const:

const int x = 3;
int *ptr = &x;     // ERROR -- enables const object to be modified through ptr
*ptr = 4;          // would modify the x object if the above were allowed

The other direction is allowed, however: creating a reference-to-const or pointer-to-const from a non-const object does not enable any new modifications:

int x = 3;
int const &ref = x;  // OK -- does not permit const object to be modified
const int *ptr = &x; // OK -- does not permit const object to be modified

The compiler only reasons about each conversion in isolation. This means that it does not allow a conversion from const to non-const even if we have some other means of modifying the underlying object:

int x = 3;
int *ptr1 = &x;          // OK -- does not permit const object to be modified
const int *ptr2 = ptr1;  // OK -- does not permit const object to be modified
ptr1 = ptr2;             // ERROR -- compiler sees that ptr2 is pointing to a
                         //          a const object, but ptr1 is not a pointer
                         //          to const

In the example above, even though ptr2 was originally initialized from ptr1, we cannot later assign the value of ptr2 to ptr1, since it would be converting a pointer-to-const to a pointer-to-non-const. This is actually useful for us as programmers: if we pass a pointer to another function, and the function guarantees that it won’t modify the pointed-to object by declaring its parameter as pointer-to-const, then we would be unhappy if the function could convert it back to a pointer-to-non-const and modify the pointed-to object. [1]

Structs

C++ has several different categories of objects:

  • Atomic types are built into the language, and these types are atomic because their objects cannot be subdivided into smaller objects. Atomic types are also known as primitive types. Examples of atomic types include basic numeric types such as int, double, bool, and char, as well as pointer types (e.g. int *, string *).

  • Arrays are contiguous sequences of objects of the same type. They are therefore composed of homogeneous subobjects. We will discuss arrays later in the course.

  • Class-type objects are objects composed of member subobjects, each which may be of a different type. Class-type objects are thus heterogeneous, and they are also often called compound objects.

In C++, a class type is introduced through the struct or class keyword. We will use the two keywords for different conventions when introducing our own data types. Later, we will see that the actual distinction between how C++ treats the two keywords is minimal.

In order to introduce a new data type, we use the struct keyword, followed by the name of the type we are introducing, followed by a body with member declarations:

struct Person {
  string name;
  int age;
  bool is_ninja;
};

Here, we are introducing a Person type. The body contains declarations for three member variables, each with their own type and name. The semicolon after the struct definition is mandatory, unlike in some other languages.

After the struct definition, we can create objects that have Person type. The following program creates two local variables of type Person:

int main() {
  Person elise;
  Person tali;
}

Each Person object has its own subobjects name, age, and is_ninja located within the memory for the Person object, as shown in Figure 21.

_images/06_person_struct.svg

Figure 21 Memory for two objects of Person type.

Since we did not explicitly initialize the Person objects, they are default initialized by in turn default initializing their member subobjects. The age and is_ninja members are of atomic type, so they are default initialized to indeterminate values. The name member is of class type, and it is default initialized to an empty string. In the future, we will see that class types can specify how they are initialized.

We can explicitly initialize a Person object with an initializer list, similar to how we can initialize the elements of a vector:

Person elise = { "Elise", 22, true };

This initializes the struct member-by-member from the initializer list: the name member is initialized with "Elise", the age member is initialized with 22, and the is_ninja member is initialized with true. If fewer initializers are provided than members, the remaining members are implicitly initialized (with zeros for atomic types).

We can also copy structs when initializing a new struct or assigning to an existing one:

Person tali = elise;

By default, copying a struct copies the members one by one. [2] The result in memory is illustrated in Figure 22.

_images/06_struct_copy.svg

Figure 22 By default, copying a class-type object copies each of the member variables.

We can access individual members of a struct with the dot (.) operator. The struct object goes on the left-hand side, and the member name on the right:

tali.name = "Tali";

Here, we have assigned the string "Tali" to the name member of the tali object. Figure 23 shows the result in memory.

_images/06_struct_member_access.svg

Figure 23 The result of modifying an individual member variable.

As the figure shows, tali and elise each have their own name members, so that modifying one does not affect the other.

We can use an initializer list for a struct in contexts other than initialization. The following uses an initializer list in an assignment (which is different from an initialization, since the target object already exists), as well as an argument to a function:

void Person_print_name(Person person) {
  cout << person.name << endl;
}

int main() {
  Person tali;
  tali = { "Tali", 21, true };               // in an assignment
  Person_print_name({ "Elise", 22, true });  // as argument to function
}

When passing a struct to a function, we have our usual default of value semantics, meaning that a copy is made. For instance, the following erroneous definition of Person_birthday() does not modify the argument object, since it receives a copy of the argument:

// MODIFIES: person
// EFFECTS: Increases the person's age by one. If they are now older
//          than 70, they are no longer a ninja.
void Person_birthday(Person person) {
  ++person.age;
  if (person.age > 70) {
    person.is_ninja = false;
  }
}

Figure 24 illustrates what happens when we call Person_birthday() on a Person object:

_images/06_struct_pass_by_value.svg

Figure 24 Passing a class-type object by value produces a copy that lives in the activation record of the callee.

The modification happens on a Person object that lives in the activation record for Person_birthday(). This copy will die when Person_birthday() returns, and the object that lives in main() is unchanged.

Instead, we need to pass the struct indirectly, either using a reference or a pointer. The following uses a pointer, and its execution is shown in Figure 25:

// REQUIRES: ptr points to a valid Person object
// MODIFIES: *ptr
// EFFECTS: Increases the person's age by one. If they are now older
//          than 70, they are no longer a ninja.
void Person_birthday(Person *ptr) {
  ++(*ptr).age;
  if ((*ptr).age > 70) {
    (*ptr).is_ninja = false;
  }
}
_images/06_struct_pass_by_pointer.svg

Figure 25 Passing a pointer to a class-type object avoids making a copy of that object.

The code uses the * operator to dereference the pointer, then uses the . operator to access a member of the resulting Person object. The parentheses around the dereference are required because the postfix . has higher precedence than the prefix *.

C++ provides the -> operator as a shorthand for dereference followed by member access. The following definition of Person_birthday() is equivalent to the one above:

void Person_birthday(Person *ptr) {
  ++ptr->age;
  if (ptr->age > 70) {
    ptr->is_ninja = false;
  }
}

Of course, this one is nicer to read and to write, so we should make use of the -> operator when possible.

The Person_birthday() function needs to modify the underlying Person object, so we cannot declare the Person as const. If a function does not need to modify the underlying object, then it should be declared as const. Declaring a struct as const prevents any of its members from being modified.

// REQUIRES: ptr points to a valid Person object
// MODIFIES: nothing
// EFFECTS: Prints a one-sentence description of the person
void Person_describe(const Person *ptr) {
  cout << ptr->name << " is " << ptr->age << " years old and ";
  if (ptr->is_ninja) {
    cout << "is a ninja!" << endl;
  } else {
    cout << "is not a ninja." << endl;
  }
}

Except for very small structs, we generally do not pass structs by value, since creating a copy of a large struct can be expensive. Instead, we pass them by pointer or by reference. If the original object needs to be modified, we use a pointer or reference to non-const. Otherwise, we use a pointer or reference to const:

void func_ptr(const Person *p);   // const can go on either side of
void func_ref(Person const &p);   // Person, but must be to the left
                                  // of * or & for the Person itself
                                  // to be non-modifiable

Compound Objects and const

Since a class-type object has a value, it can be declared as const, which prevents any of its members from being modified. As an example, consider the following struct definition:

struct Foo {
  int num;
  int *ptr;
};

Like any const object, a const Foo must be initialized upon creation:

int main() {
  int x = 3;
  const Foo foo = { 4, &x };
  ...
}
_images/06_const_struct.svg

Figure 26 Contents of a Foo object. Declaring the object as const only prohibits modifications to the subobjects contained within the memory for the object.

With foo declared as const, attempting to modify any of its members results in a compile error:

foo.num = -1;     // ERROR
++foo.ptr;        // ERROR

Modifications cannot be made to any of the subobjects that live within the memory of an object declared const. [3]

On the other hand, it is possible to modify the object that foo.ptr points to:

*foo.ptr = -1;
cout << x;        // prints -1

Since foo is const, foo.ptr is a const pointer, and the expression has type int * const. This means it is not a pointer to const, so modifying the value of the object it is pointing at is allowed. Looking at it another way, the object x lives outside the memory for foo, so the fact that foo is const has no effect on whether or not x can be modified through a pointer that lives within foo.

Abstract Data Types in C

Recall that abstraction is the idea of separating what something is from how it works, by separating interface from implementation. Previously, we saw procedural abstraction, which applies abstraction to computational processes. With procedural abstraction, we use functions based on their signature and documentation without having to know details about their definition.

The concept of abstraction can be applied to data as well. An abstract data type (ADT) separates the interface of a data type from its implementation, and it encompasses both the data itself as well as functionality on the data. An example of an ADT is the string type in C++, used in the following code:

string str1 = "hello";
string str2 = "jello";
cout << str1 << endl;
if (str1.length() == str2.length()) {
  cout << "Same length!" << endl;
}

This code creates two strings and initializes them to represent different values, prints out one of them, and compares the lengths of both – all without needing to any details about the implementation of string. Rather, it relies solely on the interface provided by the string abstraction.

A string is an example of a full-featured C++ ADT, providing customized initialization, overloaded operations such as the stream-insertion operator, member functions, and so on. We will start with the simpler model of C ADTs, deferring C++ ADTs until next time.

The C language only has support for structs with data members (i.e. member variables). While this is sufficient to represent the data of an ADT, the functions that operate on the ADT must be defined separately from the struct. The following is the data definition of an ADT to represent triangles:

// A triangle ADT.
struct Triangle {
  double a;
  double b;
  double c;
};

int main() {
  Triangle t1 = { 3, 4, 5 };
  Triangle t2 = { 2, 2, 2 };
}

The Triangle struct contains three member variables, one for each side of the triangle, each represented by a double. The example in main() creates and initializes two Triangle structs, resulting in the memory layout in Figure 27.

_images/07_triangle_struct.svg

Figure 27 Two local Triangle objects.

An ADT also includes functions that operate on the data. We can define functions to compute the perimeter of a triangle or to modify it by scaling each of the sides by a given factor:

// REQUIRES: tri points to a valid Triangle
// EFFECTS:  Returns the perimeter of the given Triangle.
double Triangle_perimeter(const Triangle *tri) {
  return tri->a + tri->b + tri->c;
}

// REQUIRES: tri points to a valid Triangle; s > 0
// MODIFIES: *tri
// EFFECTS:  Scales the sides of the Triangle by the factor s.
void Triangle_scale(Triangle *tri, double s) {
  tri->a *= s;
  tri->b *= s;
  tri->c *= s;
}

Our naming convention for functions that are part of a C-style ADT is to prepend the function name with the name of the ADT, Triangle in this case. The first parameter is a pointer to the actual Triangle object the function works on. If the object need not be modified, we declare the pointer as a pointer to const.

The following demonstrates how to use the Triangle ADT functions:

int main() {
  Triangle t1 = { 3, 4, 5 };
  Triangle_scale(&t1, 2);                   // sides are now 6, 8, 10
  cout << Triangle_perimeter(&t1) << endl;  // prints 24
}

The code creates a Triangle as a local variable and initializes it with sides 3, 4, and 5. It then scales the sides by a factor of 2 by calling Triangle_scale(). Since that function takes a pointer to the actual triangle, we use the address-of operator to obtain and pass the address of t1, as shown in Figure 28.

_images/07_triangle_scale.svg

Figure 28 Passing a pointer to a Triangle object.

The function scales each side of the triangle, resulting in t1 having sides of 6, 8, and 10. We then call Triangle_perimeter() on the address of t1, which computes the value 24.

In this example, the code in main() need not worry about the implementation of Triangle_scale() or Triangle_perimeter(). Instead, it relies on abstraction, using the functions for what they do rather than how they do it. However, in initializing t1 itself, the code is relying on implementation details – specifically, that a Triangle is implemented as three double members that represent the lengths of the sides. If the implementation were to change to represent a triangle as two sides and the angle between them, for instance, then the behavior of the code in main() would change, and it would no longer print 24. Thus, we need to abstract the initialization of a Triangle, avoiding having to initialize each member directly. We do so by defining a Triangle_init() function:

// REQUIRES: tri points to a Triangle object
// MODIFIES: *tri
// EFFECTS:  Initializes the triangle with the given side lengths.
void Triangle_init(Triangle *tri, double a_in,
                   double b_in, double c_in) {
  tri->a = a_in;
  tri->b = b_in;
  tri->c = c_in;
}

int main() {
  Triangle t1;
  Triangle_init(&t1, 3, 4, 5);
  Triangle_scale(&t1, 2);
  cout << Triangle_perimeter(&t1) << endl;
}

The user of the Triangle ADT creates an object without an explicit initialization and then calls Triangle_init() on its address to initialize it, providing the side lengths. After that call, the Triangle has been properly initialized and can be used with the other ADT functions. Now if the implementation of Triangle changes, as long as the interface remains the same, the code in main() will work as before. The code within the ADT, in the Triangle_... functions, will need to change, but outside code that uses the ADT will not. The following illustrates an implementation of Triangle that represents a triangle by two sides and an angle:

// A triangle ADT.
struct Triangle {
  double side1;
  double side2;
  double angle;
};

// REQUIRES: tri points to a Triangle object
// MODIFIES: *tri
// EFFECTS:  Initializes the triangle with the given side lengths.
void Triangle_init(Triangle *tri, double a_in,
                   double b_in, double c_in) {
  tri->side1 = a_in;
  tri->side2 = b_in;
  tri->angle = std::acos((std::pow(a_in, 2) + std::pow(b_in, 2) -
                          std::pow(c_in, 2)) /
                         (2 * a_in * b_in));
}

// REQUIRES: tri points to a valid Triangle
// EFFECTS:  Returns the first side of the given Triangle.
double Triangle_side1(const Triangle *tri) {
  return tri->side1;
}

// REQUIRES: tri points to a valid Triangle
// EFFECTS:  Returns the second side of the given Triangle.
double Triangle_side2(const Triangle *tri) {
  return tri->side2;
}

// REQUIRES: tri points to a valid Triangle
// EFFECTS:  Returns the third side of the given Triangle.
double Triangle_side3(const Triangle *tri) {
  return std::sqrt(std::pow(tri->side1, 2) +
                   std::pow(tri->side2, 2) -
                   2 * tri->side1 * tri->side2 * std::acos(tri->angle));
}

// REQUIRES: tri points to a valid Triangle
// EFFECTS:  Returns the perimeter of the given Triangle.
double Triangle_perimeter(const Triangle *tri) {
  return Triangle_side1(tri) + Triangle_side2(tri) + Triangle_side3(tri);
}

// REQUIRES: tri points to a valid Triangle; s > 0
// MODIFIES: *tri
// EFFECTS:  Scales the sides of the Triangle by the factor s.
void Triangle_scale(Triangle *tri, double s) {
  tri->side1 *= s;
  tri->side2 *= s;
}

Here, we have added accessor or getter functions for each of the sides, allowing a user to obtain the side lengths without needing to know implementation details. Even within the ADT itself, we have used Triangle_side3() from within Triangle_perimeter() to avoid code duplication.

The REQUIRES clauses of the ADT functions make a distiction between Triangle objects and valid Triangle objects. The former refers to an object that is of type Triangle but may not have been properly initialized, while the latter refers to a Triangle object that has been initialized by a call to Triangle_init(). Except for Triangle_init(), the ADT functions all work on valid Triangles.

Now that we have a full definition of a C-style ADT, we adhere to the following convention for working with one: the user of a C-style ADT may only interact with the ADT through its interface, meaning the functions defined as part of the ADT’s interface. The user is generally prohibited from accessing struct member variables directly, as those are implementation details of the ADT. This convention also holds in testing an ADT, since tests should only exercise the behavior of an ADT and not its implementation.

Representation Invariants

When designing an abstract data type, we must build a data representation on top of existing types. Usually, there will be cases where the underlying data representation permits combinations of values that do not make sense for our ADT. For example, not every combination of three doubles represents a valid triangle – a double may have a negative value, but a triangle may not have a side with negative length. The space of values that represent valid instances of a triangle abstraction is a subset of the set of values that can be represented by three doubles, as illustrated in Figure 29.

_images/07_representation_invariants.svg

Figure 29 Representation invariants define the valid subset of the values allowed by the data representation of an ADT.

Thus, when designing an ADT, we need to determine the set of values that are valid for the ADT. We do so by specifying representation invariants for our ADT, which describe the conditions that must be met in order to make an object valid. For a triangle represented as a double for each side, the following representation invariants must hold:

  • The length of each side must be positive.

  • The triangle inequality must hold: the sum of any two sides must be strictly greater than the remaining side.

Often, we document the representation invariants as part of the ADT’s data definition:

// A triangle ADT.
struct Triangle {
  double a;
  double b;
  double c;
  // INVARIANTS: a > 0 && b > 0 && c > 0 &&
  //             a + b > c && a + c > b && b + c > a
};

We then enforce the invariants when constructing or modifying an ADT object by encoding them into the REQUIRES clauses of our functions. We can use assertions to check for them as well, where possible:

// REQUIRES: tri points to a Triangle object;
//           each side length is positive (a > 0 && b > 0 && c > 0);
//           the sides meet the triangle inequality
//           (a + b > c && a + c > b && b + c > a)
// MODIFIES: *tri
// EFFECTS:  Initializes the triangle with the given side lengths.
void Triangle_init(Triangle *tri, double a, double b, double c) {
  assert(a > 0 && b > 0 && c > 0);              // positive lengths
  assert(a + b > c && a + c > b && b + c > a);  // triangle inequality
  tri->a = a;
  tri->b = b;
  tri->c = c;
}

// REQUIRES: tri points to a valid Triangle; s > 0
// MODIFIES: *tri
// EFFECTS:  Scales the sides of the Triangle by the factor s.
void Triangle_scale(Triangle *tri, double s) {
  assert(s > 0);  // positive lengths
  tri->a *= s;
  tri->b *= s;
  tri->c *= s;
}

Plain Old Data

As mentioned above, we adhere to the convention of only interacting with an ADT through its interface. Usually, this means that we do not access the data members of an ADT in outside code. However, occasionally we have the need for an ADT that provides no more functionality than grouping its members together. Such an ADT is just plain old data (POD) [4], without any functions that operate on that data, and we define its interface to be the same as its implementation.

The following is an example of a Pixel struct used as a POD:

// A pixel that represents red, green, and blue color values.
struct Pixel {
  int r; // red
  int g; // green
  int b; // blue
};

int main() {
  Pixel p = { 255, 0, 0 };
  cout << p.r << " " << p.g << " " << p.b << endl;
}

The Pixel ADT consists of just a data representation with no further functionality. Since it is a POD, its interface and implementation are the same, so it is acceptable to access its members directly.

Abstraction Layers

As with procedural abstraction, data abstraction is also defined in layers, with each layer interacting solely with the interface of the layer below and not its implementation. For example, we can represent an image using three matrices, one for each color channel. Any code that uses an image relies on the image interface, without needing to know that it is implemented over three matrices. Each matrix in turn can be represented using a single-dimensional vector. Code that uses a matrix relies on the 2D abstraction provided by the interface without needing to know that it is implemented as a 1D vector under the hood.

_images/07_abstraction_layers.svg

Figure 30 Abstraction layers for an image.

Testing an ADT

As mentioned previously, code outside of an ADT’s implementation must interact with the ADT solely through its interface, including test code. Modifying an ADT’s implementation should not require modifying its test code – we should be able to immediately run our regression tests in order to determine whether or not the ADT still works.

Adhering to the interface often means that we can’t test each ADT function individually. For instance, we cannot test Triangle_init() in isolation; instead, we can test it in combination with the side accessors (e.g. Triangle_side1()) to determine whether or not the initialization works correctly. Instead of testing individual functions, we test individual behaviors, such as initialization.

As another example, let’s proceed to design and test an ADT to represent a coordinate in two-dimensional space, using the principle of test-driven development that we saw previously. We will use polar coordinates, which represent a coordinate by the radius from the origin and angle from the horizontal axis, and we reflect this in the name of the ADT and its interface.

_images/07_polar_coordinates.svg

Figure 31 Polar representation of a point in two-dimensional space.

We start by determining the interface of the ADT:

// A set of polar coordinates in 2D space.
struct Polar;

// REQUIRES: p points to a Polar object
// MODIFIES: *p
// EFFECTS: Initializes the coordinate to have the given radius and
//          angle in degrees.
void Polar_init(Polar* p, double radius, double angle);

// REQUIRES: p points to a valid Polar object
// EFFECTS: Returns the radius portion of the coordinate as a
//          nonnegative value.
double Polar_radius(const Polar* p);

// REQUIRES: p points to a valid Polar object
// EFFECTS:  Returns the angle portion of the coordinate in degrees as
//           a value in [0, 360).
double Polar_angle(const Polar* p);

We then proceed to write some test cases, following the principles of test-driven development:

// Basic test of initializing a Polar object.
TEST(test_init_basic) {
  Polar p;
  Polar_init(&p, 5, 45);

  ASSERT_EQUAL(Polar_radius(&p), 5);
  ASSERT_EQUAL(Polar_angle(&p), 45);
}

We can then proceed to define a data representation. As part of this process, we should consider what representation invariants our ADT should have. For our Polar ADT, a reasonable set of invariants is that the radius is nonnegative, and the angle is in the range \([0, 360)\) (using degrees rather than radians) [5]:

struct Polar {
  double r;
  double phi;
  // INVARIANTS: r >= 0 && phi >= 0 && phi < 360
};

Now that we have a data representation, we can make an initial attempt at implementing the functions as well:

void Polar_init(Polar* p, double radius, double angle) {
  p->r = radius;
  p->phi = angle;
}

double Polar_radius(const Polar* p) {
  return p->r;
}

double Polar_angle(const Polar* p) {
  return p->phi;
}

We can run our existing test cases to get some confidence that our code is working. In addition, the process of coming up with a data representation, representation invariants, and function definitions often suggests new test cases. For instance, the following test cases check that the representation invariants are met when Polar_init() is passed values that don’t directly meet the invariants:

// Tests initialization with a negative radius.
TEST(test_negative_radius) {
  Polar p;
  Polar_init(&p, -5, 225);
  ASSERT_EQUAL(Polar_radius(&p), 5);
  ASSERT_EQUAL(Polar_angle(&p), 45);
}

// Tests initialization with an angle >= 360.
TEST(test_big_angle) {
  Polar p;
  Polar_init(&p, 5, 405);
  ASSERT_EQUAL(Polar_radius(&p), 5);
  ASSERT_EQUAL(Polar_angle(&p), 45);
}

Given our initial implementation, these test cases will fail. We can attempt to fix the problem as follows:

void Polar_init(Polar* p, double radius, double angle) {
  p->r = std::abs(radius);  // set radius to its absolute value
  p->phi = angle;
  if (radius < 0) {         // rotate angle by 180 degrees if radius
    p->phi = p->phi + 180;  // was negative
  }
}

Running our test cases again, we find that both test_negative_radius and test_big_angle still fail: the angle value returned by Polar_angle() is out of the expected range. We can fix this as follows:

void Polar_init(Polar* p, double radius, double angle) {
  p->r = std::abs(radius);  // set radius to its absolute value
  p->phi = angle;
  if (radius < 0) {         // rotate angle by 180 degrees if radius
    p->phi = p->phi + 180;  // was negative
  }
  p->phi = std::fmod(p->phi, 360);  // mod angle by 360
}

Now both test cases succeed. However, we may have thought of another test case through this process:

// Tests initialization with a negative angle.
TEST(test_negative_angle) {
  Polar p;
  Polar_init(&p, 5, -45);
  ASSERT_EQUAL(Polar_radius(&p), 5);
  ASSERT_EQUAL(Polar_angle(&p), 315);
}

Unfortunately, this test case fails. We can try another fix:

void Polar_init(Polar* p, double radius, double angle) {
  p->r = std::abs(radius);  // set radius to its absolute value
  p->phi = angle;
  if (radius < 0) {         // rotate angle by 180 degrees if radius
    p->phi = p->phi + 180;  // was negative
  }
  p->phi = std::fmod(p->phi, 360);  // mod angle by 360
  if (p->phi < 0) {         // rotate negative angle by 360
    p->phi += 360;
  }
}

Our test cases now all pass.