CS 509, Advanced Programming II, Spring 2001

CS 509, Advanced Programming II

Spring 2001 - Test 7

A format string is a sequence of zero or more characters, format, and escape specifications specifications delimited by double quotes.
A character may be any character except the per-cent character % and the double quote ".
A format specification begins with a per-cent character, immediately followed by an optional size specification, immediately followed by a mandatory type specification. A type specification may be any of the characters a through z in either case. A size specification consists of a sequence of one or more decimal digits, followed by a period (.) followed by a sequence of zero or more decimal digits.
An escape specification consists of the per-cent character immediately followed by a per-cent character or a double quote.
Describe an algorithm which accepts a string and determines if the entire string represents a valid format string.

This recognizer requires the input string be exactly a format string. Upper case letters represent both cases.
A colleague of yours has written the following class
```
class point {
  // blah blah blah
  point & operator=(const point & p) const {
    cerr << "in point=\n";
    // blah blah blah
    }
  // blah blah blah
  };
```
and it seems to work correctly. The program
```
int main(void) {
  point p1, p2;
  // blah blah blah
  p1 = p2;
  // blah blah blah
  }
```
produces the expected output on std-err. However, when your colleague ran the program
```
int main(void) {
  point * p1 = new point;
  point * p2 = new point;
  // blah blah blah
  p1 = p2;
  // blah blah blah
  }
```
no output appeared on std-err. Mystified by this behavior, and recognizing your expertise in C++ operator overloading, your colleague comes to you for an explanation. What do you say?
Your colleague has forgotten that the types T and pointer to T are two different types. Defining the assignment operator
```
point operator=(const point p)
```
(I've omitted the reference indicators & for clarity) does not define the assignment operator
```
point * operator=(const point * p)
```
In class we talked about implementing a 2-dimensional matrix class as a one-dimensional array; that is, instead of implementing
```
knows["tristan"]["isolde"]
```
we implemented
```
knows["tristan isolde"]
```
Explain briefly how you would use operator overloading to implement a true 2-dimensional matrix class.
Do not go into details for this question, because there are a lot of them; just briefly explain the classes you'd use and the way you'd use them to overload operator[] to provide a 2-dimensional matrix data type.
Probably the easiest way to answer this question is to parenthesize the expression
```
knows["tristan"]["isolde"]
```
as it would be evaluated by the compiler:
```
(knows["tristan"])["isolde"]
```
Let knows be a value of type Matrix. The Matrix type defines operator[], which returns some value v (assuming no indexing errors). This reduces the previous expression to
v["isolde"]
What can we say about this expression? First, it must return a value of the type of the elements in Matrix. What is the type of v? It can't be of type Matrix because that would mean the first indexing operator Matrix::operator[]'s return type is the same as the matrix-element type, which would require that all matrix-element types used must respond to the indexing operator (also, it would result in infinite recursion). v's type has to be some new type, intermediate between Matrix and the type of the matrix elements.
Although v could be many types, two of the most natural types for v are MatrixColumn and MatrixRow; that is, the type of the value knows["tristan"] is a row (or a column) of the matrix indexed by "tristan". In addition to being natural, making the intermediate type be MatrixRow would be consistent with the definition of multi-dimensional arrays in C++.
The classes and operator[] definitions are
```
class Matrix {
  MatrixRow & operator[](IndexType &);
  };

Class MatrixRow {
  ElementType & operator[](IndexType &);
  };
```
There are many other details that need to be filled in here - what's the relation between Matrix and MatrixRow? How are ElementType and IndexType indicated? and so on - but the important idea is to define an intermediate type half-way between Matrix and ElementType.
A couple of people suggested using the pair data type to represent the two index values using a single array operator:
```
ElementType Matrix::operator[](const pair<IndexType, IndexType> & p);
```
I accepted this as an answer, but it's not really a 2-dimensional array because it doesn't treat each dimension separately, as the example given above and C++ does.
It is amusing to note that you can give a similar implementation by overloading the comma operator:
```
IndexType operator,(const IndexType & i, const IndexType & j);

ElementType Matrix::operator[](const IndexType & i);
```
An example use is
```
knows["tristan", "isolde"]
```
The operator, would take the two index values and munge them into one for use by operator[]; in our example, it would catenate the two indices in order with a space between them:
```
"tristan", "isolde" == "tristan isolde"
```
As indicated by the prototype, the operator, cannot be a member function of Matrix (why?); also the possible types for IndexType are restricted (to what? and why?). This problem also doesn't treat the matrix as a 2-dimensional entity.
It is even more amusing to note that we can also solve this problem by overloading operator():
```
MatrixRow Matrix::operator()(const IndexType & i);

ElementType Matrix::operator()(const IndexType & i, const IndexType & j);
```
This solution has the advantage of treating the matrix as a 2-dimensional entity.
A couple of your colleagues are trying to overload the postfix operator++ and are running into a few problems. First they tried
```
class C {
  // blah blah blah
  void operator ++ (const C & obj);
  // blah blah blah
  }
```
And got an error about having an int as the second parameter. Then they tried
```
class C {
  // blah blah blah
  void operator ++ (const C & obj, int i);
  // blah blah blah
  }
```
and got an error about having too many arguments. Recognizing the skillful way in which you handled question 2, they come to you for explanations. How do you explain each of the error messages, and what do you tell them is the correct resolution to their problem?
Your colleagues' problem arises because they forgot about the magic integer argument that differentiates between prefix operator++ and postfix operator++. They also apparently forgot that, in a class operator overloading, the first argument is implicit defined by the compiler and should not be included in the argument list.
The first error occurred because the argument type is wrong: it's an argument of type C & when it should be an argument of type int.
The second error occurred when your colleagues mis-interpreted the error message and added a second (really a third) argument to the operator definition, giving the operator too many arguments.
Their problem can be correctly resolved by giving a single actual augment of type int:
```
void operator++(int);
```

This page last modified on 26 April 2001.