January 1998 Programmer's Challenge

Cell Selection

Mail solutions to: progchallenge@mactech.com
Due Date: 11:59pm EDT, Thursday, 1 January 1998

One year ago, the Macintosh world was full of rumors about the prospect of Apple acquiring the Be Operating System. MacTech bundled the DR8 BeOS CD-ROM with the magazine. The Challenge column invited readers to try the BeOS on their Macs and enter the first BeOS Challenge. Then, before the BeOS issue had even arrived, Apple announced its intention to buy NeXT, and the journey to Rhapsody began.

Even though BeOS has faded from the headlines, it runs better on your Mac than it ever did. In fact, Preview Release 2 is scheduled to arrive in the immediate future. [In fact, it's available now for download at the Be web page .] My personal interest in BeOS has been reinvigorated by a recent bargain that was too good to pass up Ða dual 200MHz 604e MaxPOWR 400 processor upgrade. While it is possible for developers to take advantage of multiple processors under Mac OS, using a special nonsymmetric interface developed in conjunction with DayStar, multiprocessing Mac OS applications are the exception rather than the rule. Not so, of course, with BeOS, where symmetric multiprocessing is an intrinsic part of the operating system.

In honor of the one-year anniversary of the MacTech BeOS issue, and in celebration of my new 2x200 MHz toy, the Challenge this month is going to encourage the use of multiple processors. You will be able to use either BeOS or Mac OS. If you choose to use Mac OS and wish to take advantage of the second processor on my test system, you should use the SDK found at dev.apple.com.

The problem this month, suggested by Jon "h++" Wätte, is to implement a CellSelection class. CellSelection implements a two-dimensional set of cells, each of which can be "on" or "off", along with a collection of methods to manipulate cell states.

The prototype for the code you should write is:

#if __dest_os == __be_os
#include <SupportDefs.h>
#else
typedef long int32;
typedef unsigned long uint32;
#endif

struct Area {
int32 left,top,right,bottom;
/* Area coordinates are inclusive. {2,2,3,4} includes 6 cells. */
/* Any area with left>right or top>bottom is empty. */
};

class CellSelection {
private:
/* add your methods and instance variables here */
public:
CellSelection(void);
/* create an empty selection */
~CellSelection(void);
/* free any allocated memory */
bool Clear();
/* make the selection empty */
bool Add(Area area);
/* add the area of cells to this selection */
bool Remove(Area area);
/* remove the area of cells from this selection */
bool Invert(Area area);
/* remove cells in the area that are also in this selection
and add the area cells that are not in this selection */
bool Add(const CellSelection & otherSelection);
/* add the otherSelection to this selection */
bool Remove(const CellSelection & otherSelection);
/* remove the otherSelection from this selection */
bool Invert(const CellSelection & otherSelection);
/* remove cells in the otherSelection that are also in this selection
and add the otherSelection cells that are not in this selection */
bool AllSelected(Area area);
/* return TRUE if all cells in the area are selected */
uint32 CountSelected(Area area);
/* count cells that are "on" */
bool EqualSelected(const CellSelection & otherSelection);
/* return TRUE if otherSelection equals this selection */
};

The destructor should free any memory allocated by the constructor or by any of the methods of CellSelection. The Add method should turn on any cells in the area or otherSelection; similarly the Remove method should turn off the specified cells. Invert is an exclusive-or operator that turns off cells that are on and turns on cells that are off, provided the cell is in the specified area or otherSelection. The Clear method resets the selection to its original empty state. All of these methods return TRUE if they succeed or FALSE if they run out of memory. The AllSelected method determines whether all of the cells in the specified area are on, while the CountSelected method counts the number of cells in the specified area that are on. Finally, the EqualSelected method determines whether the selected cells in this CellSelection are the same as the selected cells in the otherSelection.

The test code will require you to create a modest number of CellSelection instances (perhaps 10 to 50) and manipulate them with a larger number of Add/Remove/Invert operations, interspersed with a modest number of AllSelected/CountSelected/EqualSelected tests.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions must be coded in C++, written for either the Macintosh operating system or the Be operating system. You can use all of the available memory in my 96MB 8500, but your code must fail gracefully if it runs out of memory. Your solution should include a complete CodeWarrior project file and test driver, compressed into a .sit or .cpt archive (for MacOS) or into a .zip, .gz archive (for BeOS). I'll evaluate your solution using the target operating system you designate, and the fastest correct solution will be the winner.

Memory-inefficient solutions that fail to handle large problems will be considered less correct than memory-efficient solutions.