218 Third Test, 27 April 99

The Question

Bill Gates (All characters are fictional; any resemblance to real persons, living or dead, is purely coincidental.) has been arrested by the Feds and given a 5,000 year sentence in Alcatraz for crimes against humanity. You are part of the programming team responsible for re-implementing windows properly. The first stage is to define C++ classes that represent a computer's screen and the windows displayed on it.

You must define two classes: one called "window", that represents an individual window and records its size and position, and one called "screen" that represents the whole screen and records its size together with the collection of windows that are visible on it. One of your colleagues started the definition of "screen", but ran away before he finished. You may make use of his work:

class screen
{ protected:
    window *window_list[10];
    int num_windows;
    int width, height;
  public:
    screen(int w, int h);
    void add(window *x);
    void remove(window *x);
    window *find_window_at(int x, int y);
    void print(void); }

screen::screen(int w, int h)
{ width=w; height=h;
  for (int i=0; i<10; i+=1)
    window_list[i]=NULL;
  num_windows=0; }

void screen::add(window *x)
{ if (num_windows>=10)
  { fprintf(stderr,"Too many windows on screen\n");
    exit(1); }
  window_list[num_windows]=x;
  num_windows+=1;
  x->parent=this; }

The constructor's purpose should be obvious. The "add" method is used to add a window (that has already been created) to the screen. Every window has a member called "parent" which should always point to the screen that contains the window; that is the reason for the last assignment in the "add" method.

You must define the three remaining methods. "Remove" is the opposite of "add": give it a pointer to a window and it should remove that window from its list. "Find_window_at" is the method that is called when the user clicks a mouse button: give it x and y coordinates on the screen, and it searches through its list of windows to find the one that covers that position. "Print" is simply for debugging; it should print out the size of the screen, and a description of every window on that screen.

You will probably want to define the "window" class before defining these three methods. You should at least read the following description of the window class first.

The class "window" should have at least six members: integers "x" and "y" to represent the coordinates of the top left corner of the window; integers "width" and "height" to represent the size of the window; a string to store the name of the window, and a pointer-to-screen to represent the screen that this window appears on. You must define the class, and the following methods:

A constructor that takes a name and initial values for x, y, width, and height.
void moveto(int newx, int newy); which is used to change the position of the window without changing its size.
void resize(int new_width, int new_height); which is used to change the size of the window without changing its position.
void resize(float proportion); which also changes the size of the window to a particular fraction of its original size, so resize(0.5) should halve both height and width, resize(1.1) should increase its dimensions by 10%, etc.
void swallow(window *x); which should change the size, and perhaps also position, of this window so that it completely covers both its own original screen area and the area covered by window x. It should also remove window x from the screen.
void print(void); which should simply print the name, position, and size of the window in a human readable form.

Here is an example of the classes in use, so you can see how they should behave:

void main(void)
{ screen scr(640,480);                     // just a little old VGA monitor
  window *w1, *w2, *w3, *w4;
  w1=new window("One", 0, 0, 200, 100);    // creates a new window named "One";
  scr.add(w1);            // it is in the top left corner of the screen (x=0, y=0)
                          // and is 200 pixels wide and 100 pixels high.
  w2=new window("Two", 220, 0, 100, 100);  // a new window called "Two", just to
  scr.add(w2);            // the right of the first, and half the width.
  w1->moveto(0,100);      // the first window is moved to position (x=0, y=100)
  scr.print();         // Should make it print out something like this...
             // Screen size 640x480, contains 2 windows
             // Window "One" at 0,100, size=200x100
             // Window "Two" at 220,0, size=100x100
  w3=new window("Three", 400, 300, 200, 150);
  scr.add(w3);       // new window at (x=400, y=300) size 200 wide, 150 high;
  w4=new window("Four", 120, 200, 200, 200);
  scr.add(w4);       // new window at (x=120, y=200) size 200 wide, 200 high;
  w1->resize(0.75);  // first window changed to three quarters of its original size
           // see picture 1
  w3->swallow(w2);
           // w3 must cover the area originally covered by w3 and w2. w3 was at
           // (x=400, y=300) and reached to (x=600, y=450). w2 was at (x=220, y=0)
           // and reached to (x=320, y=100). To cover all of that, w3 must move to
           // (x=220, y=0) and reach to (x=600, y=450), so its size is 380x450.
           // see picture 2
  window *temp=scr.find_window_at(150,300);
  temp->print();       // window w4 ("Four") covers screen position (x=150, y=300)
                       // so this should print a description of window "Four".
  scr.print();    // Should make it print out something like this...
             // Screen size 640x480, contains 3 windows
             // Window "One" at 0,100, size=150x75
             // Window "Three" at 220,0, size=380x450
             // Window "Four" at 120,200, size=200x200
  scr.remove(w1);      // now w1 is removed, so only w3 and w4 remain.
  scr.print();    // Should make it print out something like this...
             // Screen size 640x480, contains 2 windows
             // Window "Three" at 220,0, size=600x450
             // Window "Four" at 120,200, size=200x200

(pictures omitted because HTML isn't that flexible)

The Answers

Defining the Window class. We have been told what members are to be provided, and what methods, so the class declaration should be easy:

class window
{ protected:
    int x, y, width, height;
    char *name;
    screen *parent;
  public:
    window(char *name0, int x0, int y0, int width0, int height0);
    void moveto(int newx, int newy);
    void resize(int new_width, int new_height);
    void resize(float proportion);
    void swallow(window *x);
    void print(void); };

The constructor hardly has to do anything; just initialise the members appropriately:

window::window(char *name0, int x0, int y0, int width0, int height0)
{ name=new char[strlen(name0)+1];
  strcpy(name,name0);
  x=x0;
  y=y0;
  width=width0;
  height=height0;
  parent=NULL; }

The next two methods are even easier; A window's position is stored in its x and y members and nowhere else. If you want to change its position, all you have to do is change its x and y, and that's it. The same goes for changing its size:

void window::moveto(int newx, int newy)
{ x=newx;
  y=newy; }

void window::resize(int new_width, int new_height)
{ width=new_width;
  height=new_height; }

We could have gone totally overboard and put in all sorts of error checking. For instance, we might decide that x, y, width, and height must never be negative and that the far edges (right and bottom) must never be off the edge of the parent screen. To do that, we could write:

int window::is_ok()
{ if (x<0 || y<0 || width<0 || height<0)
    return (0);
  if (x+width > parent->width ||
      y+height > parent->height)
    return (0);
  return (1); }

And then call that method after every change to see if everything is OK.
The question is "why"? Why would you do all that extra work? You were not told to make any such checks, and the question as asked doesn't give you any reason to believe that there is anything wrong with windows that go over the edge of the screen. Most windowing systems allow that sort of thing. Don't invent extra work. Exams have quite enough questions already without you inventing new ones.

The version of resize that takes a floating point proportion is also simple, but you have to remember that you can't just assign a float value into an int variable; the compiler will whine at you. You have to convert the type explicitly:

void window::resize(float proportion)
{ width=(int)(width*proportion);
  height=(int)(height*proportion); }

All print has to do is print out the essential information. Nothing to it:

void window::print(void)
{ printf("  Window \"%s\" at %d,%d, size=%dx%d\n", name, x, y, width, height); }

All of those methods are really simple. Don't let that trick you into thinking you have missed something. A test will often have some very simple parts, just to test that you know how to do the really vital things, then some trickier parts to test your thinking a bit further. Swallow is a little bit trickier, but not much.

When one window swallows another, it takes on a size that covers the original positions of both itself and the swallowed window. To do that, we have to find the leftmost, topmost, rightmost, and bottommost edges of both windows, use those as the edges of the resized window. If we assume the existence of two functions "min" and "max", whcih do what their names suggest, it isn't too difficult. Just remember that although x and y do tell us the left and top edges of a window, the right and bottom edges have to be calculated as x+width and y+height.
(There is one tiny little complication. I'll avoid it for now, by changing the name of this method's parameter from x to w. I'll explain the complication soon):

void window::swallow(window *w)
{ int left=min(x, w->x);
  int top=min(y, w->y);
  int right=max(x+width, w->x+w->width);
  int bottom=max(y+height, w->y+w->height);
  x=left;
  y=top;
  width=right-x;
  height=bottom-y;
  parent->remove(x); }

That last statement is because the question said that the swallowed window should be removed from the screen. Screens have a remove method, and the current window's parent is obviously the screen in question.

The complication: if I had not changed the parameter's name to w, the expression for the leftmost edge would have been min(x, x->x) which is not only confusing, but also wrong. "x" can't mean two things at once. If we use x as the name of a method's parameter, we can not also use it to refer to a class member at the same time. The simplest solution is exactly what I did above: change the parameter's name. If you don't want to do that (although I can't imagine why you wouldn't), you can use "this" instead. The variable "this" is automatically declared inside every method, and is always a pointer to the current object, so every use of "x" to refer to the member x could be replaced by "this->x".

We can't just assume that useful functions exist. min and max must be defined, but that is trivial:

int min(int a, int b)
{ if (a<b) return a; else return b; }

int max(int a, int b)
{ if (a>b) return a; else return b; }

Now for the screen class. The question provided us with the beginning:

class screen
{ protected:
    window *window_list[10];
    int num_windows;
    int width, height;
  public:
    screen(int w, int h);
    void add(window *x);
    void remove(window *x);
    window *find_window_at(int x, int y);
    void print(void); }

screen::screen(int w, int h)
{ width=w; height=h;
  for (int i=0; i<10; i+=1)
    window_list[i]=NULL;
  num_windows=0; }

void screen::add(window *x)
{ if (num_windows>=10)
  { fprintf(stderr,"Too many windows on screen\n");
    exit(1); }
  window_list[num_windows]=x;
  num_windows+=1;
  x->parent=this; }

All we have to do is provide the definitions of remove, find_window_at, and print.

Remove has to be compatible with add. If we have five windows (A, B, C, D, E) and remove the third (C), then add another (F), we must be left with five windows (A, B, D, E, F) again. When remove gets rid of C, it must move D and E up to fill in the space. If we just reduce the variable "num_windows", the next add operation will just overwrite the last window.
Remove should first look through the array "window_list" to find the unwantde window. It should then move all later windows up by one, and finally reduce "num_windows":

void screen::remove(window *w)
{ int i, pos=-1;
  for (i=0; i<num_windows; i+=1)
  { if (window_list[i]==w)
    { pos=i;
      break; } }
  if (pos==-1)  // no such window to remove
    return;
  for (i=pos; i<num_windows-1; i+=1)
    window_list[i]=window_list[i+1];
  num_windows-=1; }

Find_window_at must look through the list of existing windows, testing each to see if the given co-ordinates (x, y) are within its area. That is not too difficult like this:

window *screen::find_window_at(int x, int y)
{ int i;
  for (i=0; i<num_windows; i+=1)
  { window *w=window_list[i];
    if (x>=w.x && y>=w.y && x<=w.x+w.width && y<=w.y+w.height)
    { return (w); } }
  return (NULL); }

And that is a perfectly fine solution. It would be a lot neater if each window could simply be asked "do you contain this point?", so an alternative solution would be to add to the window class a "contains" method that returns 0 for no and 1 for yes:

int window::contains(int xpos, int ypos)
{ int right=x+width;
  int bottom=y+height;
  if (xpos>=x && xpos<=right && ypos>=y && ypos<=bottom)
    return (1);
  else
    return (0); }

window *screen::find_window_at(int x, int y)
{ int i;
  for (i=0; i<num_windows; i+=1)
  { window *w=window_list[i];
    if (w->contains(x,y))
    { return (w); } }
  return (NULL); }

This is slightly more readable, but certainly not required on the test.

Finally, we just have to design the print method for a screen; it should print out the screen's details, followed by the details of each window on the screen. Windows know how to print themselves, so we don't have to do much:

void screen::print(void)
{ int i;
  printf("Screen size %dx%d, contains %d windows\n", width, height, num_windows);
  for (i=0; i<num_windows; i+=1)
  { window_list[i]->print(); } }

And that's all it took.

The Extra Credit Bit

For this, you had to remove the limit on the number of windows that a screen can hold. It is not good enough to remove the "if (num_windows>=10)" from screen::add, because window_list is still just an array of 10 pointers. Instead we should use either a growable array or a linked list:

Using a growable array, we would change the beginning of the screen class definition to:

class screen
{ protected:
    window **window_list;
    int num_windows;
    int window_list_size;
    int width, height;
  ...

and the constructor becomes:

screen::screen(int w, int h)
{ width=w; height=h;
  window_list=new (window *)[10];
  for (int i=0; i<10; i+=1)
    window_list[i]=NULL;
  window_list_size=10;
  num_windows=0; }

and "add" is modified thus: void screen::add(window *x) { if (num_windows>=window_list_size) { window_list_size=num_windows+10; window **temp=new (window *)[window_list_size]; int i; for (i=0; i<num_windows; i+=1) temp[i]=window_list[i]; for (i=num_windows; i<window_list_size; i+=1) temp[i]=NULL; delete[] window_list; window_list=temp; } window_list[num_windows]=x; num_windows+=1; x->parent=this; }
If you want to use a linked list, we would have to define a special "list-of-window" class:

class list_of_windows
{ public:
    window *this_window;
    list_of_windows *next;
    list_of_windows(void) { this_window=NULL; next=NULL; } };

And screen would have to be modified again, changing the beginning of the class:

class screen
{ protected:
    list_of_windows *window_list;
    int width, height;
  ...

and the constructor becomes:

screen::screen(int w, int h)
{ width=w; height=h;
  window_list=NULL; }

Which is a lot smaller, and "add" is modified thus: void screen::add(window *x) { list_of_windows *temp=new list_of_windows(); temp->this_window=x; temp->next=window_list; window_list=temp; x->parent=this; } Which is also nice and easy. Sadly, we would also have to modify remove. It would have to search through the list of windows until it finds the unwanted one, then modify the "next" pointer of the previous link to skip over the found one:

void screen::remove(window *w)
{ list_of_windows *ptr=window_list;
  list_of_windows *prev=NULL;
  while (ptr!=NULL &&ptr->this_window!=w)
  { prev=ptr;
    ptr=ptr->next; }
  if (ptr==NULL)     // no such window found
    return;
  if (prev==NULL)    // removeing very first window
    window_list=ptr->next;
  else
  { prev->next=ptr->next;
    delete ptr; } }

Which is perhaps not the simplest thing in the world, but we've all seen much worse. As far as the test was concerned, linked lists and growable arrays are equally acceptable. For your pruposes, a growable array would be best because it involves less work. The two other screen methods, find_window_at and print would also need to be modified to work with a linked list of windows, and that would add up to quite a lot of extra work.