TweetFollow Us on Twitter

PROGRAMMER's CHALLENGE

Volume Number: 18 (2002)
Issue Number: 12
Column Tag: PROGRAMMER's CHALLENGE

PROGRAMMER's CHALLENGE

by Bob Boonstra

Farewell

As I announced last month, this will be my last Programmer's Challenge column. I thought I would close out my tenure with a retrospective on the past seven and one-half years and the contestants, the Challenge problems, the evolution of the column, and my experiences writing it.

When I first started participating in the Challenge back in 1993, the Macintosh computer and the development environments that supported it were very different from what they are today. All entries were all 680x0 code. We used compilers from both Metrowerks and Symantec, admitting code in Pascal as well as C. When I was fortunate enough to fare well in the contests, it was due to both a reasonably good algorithm and to well-tuned C code, tweaked by analyzing the disassembled code and fooling the compiler into squeezing out an instruction or two.

By October 1995, a few months after I started writing the column, the PowerPC had been out long enough that we were able to convert the Challenge to PPC code without losing too many potential contestants. The move to PowerPC led to the demise of the annual assembly language Challenges, as fewer people were able to compete with a compiler at generating PPC code. We continued to accept Pascal solutions as long as possible, but with the demise of Symantec and the deprecation of the Metrowerks Pascal compiler, Pascal was no longer a practical option. At the request of readers, we structured some problems to accommodate entries in other development environments like REALbasic, but we only received a few entries using these environments. During the heyday of BeOS (may it rest in peace), we even ran a few Challenges using that operating system.

Over time, the power of my test machine grew, from a 6100/60 that I clock-chipped to run at 80 MHz, to a 7200/90, to an 8500 that was gradually upgraded with a sequence of processor upgrades, to the G4/500 that I use today, with a variety of PowerBooks thrown in for good measure. Sadly, the dual 1.25 GHz processor system currently on order will not arrive in time for use in the Challenge.

The Challenge had always accepted solutions via email, but it originally also allowed solutions to be submitted by physical mail, although, to the best of my knowledge, no one ever submitted one this way. Mike Scanlin and I both answered questions about the problems via email. I became concerned that not everyone had access to these answers. In December, 1995, Neil Ticktin and I decided to create an email distribution list for the Challenge, and that list became so essential that I cannot imagine running the column without it. Besides enabling us to provide answers to questions for everyone, the list allowed us to distribute the problem on a regular schedule, avoiding publication delays with the physical magazine that often resulted in the problem being printed after solutions were due!

The Challenge prizes also evolved over time. Originally the prize was $50 cash and a "Programmer's Challenge WINNER" t-shirt. For me, the t-shirt provided bragging rights, and the cash would provide (part of) an evening out with my spouse, ever patient with the hours consumed solving Challenge problems. At some point, the t-shirts went away, and the prize was increased to $100, redeemable at DevDepot. No longer useful at restaurants, perhaps, but the credit would buy twice as many toys!

The Challenge began to be dominated by regular participants, whose participation and dedication were fantastic. At the same time, we became concerned that their dominance might be discouraging to new readers thinking about mounting a Challenge, so to speak. We experimented with splitting the prize, with half going to the traditional winner, and half going to the top placing contestant who hadn't won a Challenge recently. The prize was split in this fashion a few times, but we also had some newcomers that won the Challenge outright, winning the entire prize.

In September 1997, we began offering test code with most of the Challenges. Prior to then, each contestant had to supply his/her own test drivers and test data to develop and verify their solution. As the problems became more difficult over time, more and more effort was required to create test code. Although I had always needed to write code to evaluate Challenge entries, producing test code that was useable by others, and doing so early enough to be useful to contestants, proved to be increasingly difficult. In the minds of some readers, the test code became an entitlement, and at least one declined to participate unless test code was provided. On many occasions, readers submitted their own test code, and I would often incorporate or adapt their offerings into the final test code. I would be remiss if I failed to acknowledge the readers who also helped debug the test code, more frequently than I would care to admit. Ernst Munter, besides being a frequent and successful participant in the Challenge, was especially helpful in contributing to and debugging test code.

With the regular availability of test code, we needed a way to distribute it. We set up an ftp site at MacTech, but there were some startup problems that were difficult to resolve from 3000 miles away. So I set up a Challenge section at my personal site (http://www.windmillsw.com), and began posting the test code there. Eventually, I would post the problems, the test code, and eventually the winning solutions at both the MacTech site (http://www.mactech.com/progchallenge/>) and at my personal site.

With the addition of test code, the mailing list, and the web site, writing the column changed from being a one-weekend-a-month effort to a constant activity. Writing the column itself involved selecting a problem that was both interesting and solvable in a limited amount of time. Whether I succeeded at either is for you to judge, but my perception is that I became less successful at the latter over time. Ideas for problems came from many sources, including suggestions from readers, and even suggestions from my family. Sometimes the idea sounded great when I wrote the article, but less great when I sat down to write the test code and provide test data. The March, 1998, "Help Peter Get Home" Challenge comes to mind, where I needed to create airline schedules for a Traveling Salesperson style problem, and resorted to reverse engineering Official Airline Guide data. Test code for the November, 1999, Putting Green problem was also Challenging, as I needed to create a physics model for a golf ball rolling along the green. We ran a number of contests that pitted one contestant against another, competing in games from Stratego, to Trilite, to Chess. Problems included test-based Challenges (e.g., August, 2000, Longest Word Sort), research problems (e.g., December, 1999, Costas Arrays), graphics problems (e.g., August, 1999, 3D Fly-By), more physics problems (e.g., Caribbean Cruising in August, 2001), puzzles (e.g., the June, 1999, Tetraminx and June, 2000, R*bik Rotation Challenges), and general algorithmic Challenges (e.g., October, 2000, What Bills Did They Pay). On a few occasions, the problems attracted no entries (e.g., the September, 2001, Nassi-Schneiderman Challenge). And in at least one case, I think the problem was actually unsolvable (the July, 2000, RAID 5+ problem).

It is hard to say which problem might have been my favorite, but the May 2002, Jigsaw Puzzles may have been the most satisfying. It started as one of those problems that sounded great, but providing test data turned out to be very difficult. Fortunately, with the help of the Graphing Calculator, I was able to generate reasonably interesting puzzle pieces that actually resembled a real jigsaw puzzle.

The Challenge has always been focused on efficiency, and on the Macintosh. Occasionally I would receive suggestions for changing that focus. I would receive suggestions from PC readers who wanted to remove the Mac orientation. I heard from readers who wanted the problems to be focused on practical applications and not on efficiency. We tried to vary the problems so that there would be something of interest to many people, but without forgetting that MacTech is, after all, a Macintosh magazine, and without losing the interest in programming efficiency that has been part of the Challenge from the beginning.

If you haven't written for a print magazine before, you might not appreciate the importance of publication deadlines. When I first began writing the column, the article was due at MacTech mere days after the solutions were submitted. That resulted in a number of all-night sessions to complete the scoring and write the column, and began to interfere with the Real Job. Eventually Neil and I altered the format so that the column included the solution from three months earlier, instead of two months earlier, giving me a reasonable amount of time to evaluate entries. But, being a procrastinator by nature, and increasingly busy, I still found myself trying the patience of my editor and bumping right up against the deadline. In one case, January 2002, I actually missed the deadline, and the Challenge column did not appear in the magazine. My apologies to Jessica for making her life difficult, and my thanks for her patience over the years.

I would not have been able to write the column without the support of my wife, Sharon. Besides patiently putting up with all of the time spent on the Challenge, she helped me through many a mental block by suggesting a Challenge concept, and also proofread many of the columns, catching numerous errors. Any errors that remained, of course, are my responsibility, but they were far fewer than would have been the case without her help.

In all of my time authoring the column, to the best of my knowledge I misplaced only one solution, the November, 1995 entry by Greg Linden to the Enclosing Bounds Challenge. As long as I am apologizing, I owe one to Greg. Sorry about that!

Finally, I would like to express my appreciation to everyone who participated in the Challenge over the years. More than one hundred people have placed in the top three finishers for at least one Challenge, and I have listed them all later in the column. Special thanks go to our regular participants, Ernst, Tom, Randy, Xan, Willeke, Allen, Jeff, Jonathan, Sebastian, Bill, Gustav, Alan, Peter, Tony, Ludo, and many others. Our all-time champion, Ernst Munter, has participated in 83 Challenges, and won an astounding 30 of them. Many of you have become regular email correspondents, and - while I have not met most of you - have become friends. I hope you have enjoyed reading the column and participating in the Challenge as much as I have enjoyed authoring it. Please do keep in touch.

Winner of the October, 2002 Challenge

Congratulations to Jonny Taylor (Oxford, U.K.) for taking first place in the October, 2002, Area Challenge. This problem presented readers with a rectangular grid that was to be covered with rectangles of specified areas. Cells in the grid were either empty or contained an integer. Nonempty cells were to be covered by a rectangle with an area equal to the value in the cell. Each cell had to be covered by one and only one rectangle. The Challenge was to cover the grid with rectangles satisfying the area constraints as quickly as possible.

Jonny's solution is very well commented, and I will only go over the highlights of his strategy. Jonny calls the nonzero cells in the grid Anchors. Each Anchor has associated with it a number of Shapes, or rectangles that can legally cover that Anchor. One key to the speed of Jonny's solution seems to be the iteration of steps 1 and 2 described in his commentary. His solution calculates the intersection of all Shapes that can cover each Anchor. Since the rectangle covering an Anchor must contain all of the cells in this intersection, any Shape covering another Anchor cannot include a cell in this intersection. By iteratively calculating the Anchor intersections, eliminating Shapes that violate the intersection constraint, and thus enlarging the intersection for the Anchor associated with the eliminated Shape, Jonny reduces the size of the search needed to resolve the remaining ambiguities.

Alan Hart employs a recursive approach that caches a list of legal rectangles with a given cell as the top-left corner of the rectangle. His solution was about one-third slower than the winning entry. Ernst Munter used an exhaustive search, and Tom Saxton used a recursive approach. Both Ernst and Tom provided interesting optional graphical displays (not active during timed tests) of the progress of their solutions.

The table below lists, for each of the solutions submitted, the execution time in seconds required to solve my set of test cases. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one.

   Name                     Time          Language
                            (secs)
   Jonny Taylor(90)         0.175         C++
   Alan Hart(59)            0.232         C++
   Ernst Munte232r(902)     9.959         C++
   Tom Saxton(230)          4784.882      C++

Top Contestants ...

Normally, in this spot we would list the contestants who had accumulated 20 or more points during the past two years. This being my last Challenge column, I thought I would list everyone who had placed first, second, or third in any Challenge since the column started back in 1992. The table lists the total number of points earned since the beginning of the Challenge, with 20 points being awarded for each win, 10 for each 2nd place finish, and 7 / 4 / 2 points for each 3rd, 4th, and 5th place finish, respectively. My thanks to everyone who has participated over the years, and congratulations to those who have earned a win. I hope you have enjoyed participating as much as I have enjoyed running the Challenge.

Rank  Name                 Points (Total)    Wins  2nd 3rd
 1.   Munter, Ernst        909  30  23   5
 2.   Saxton, Tom          234   7   5   4
 3.   Boonstra, Bob        176   6   2   4
 4.   Boring, Randy        144   3   2   6
 5.   Gregg, Xan           140   5   1   2
 6.   Rieken, Willeke      134   4   3   2
 7.   Stenger, Allen       118   1   4   3
 8.   Mallett, Jeff        114   3   4   2
 9.   Taylor, Jonathan     110   4   1   2
10.   Maurer, Sebastian    108   3   3   2
11.   Karsh, Bill           90   3   1   2
12.   Larsson, Gustav       87   4   0   1
13.   Hart, Alan            69   1   3   1
14.   Lewis, Peter          67   2   1   0
15.   Nicolle, Ludovic      62   1   1   4
16.   Shearer, Rob          62   1   0   4
17.   Cooper, Greg          61   1   2   3
18.   Nepsund, Ronald       57   2   1   1
19.   Cutts, Kevin          57   0   3   1
20.   Riha, Stepan          51   1   2   1
21.   Wihlborg, Claes       49   2   0   1
22.   Goebel, James         49   2   0   0
23.   Murphy, ACC           44   1   2   0
24.   Heithcock, JG         43   0   3   1
25.   Kasparian, Raffi      42   2   0   0
26.   Vineyard, Jeremy      42   2   0   0
27.   Lengyel, Eric         40   2   0   0
28.   Darrah, Dave          31   1   0   0
29.   Day, Mark             30   1   1   0
30.   Landry, Larry         29   1   0   1
31.   Schotsman, Jan        28   0   1   2
32.   Beith, Gary           28   1   0   0
33.   Cooper, Tony          27   1   0   1
34.   Slezak, Ken           26   0   2   0
35.   Sadetsky, Gregory     24   0   2   0
36.   Antoniewicz, Andy     24   1   0   0
37.   Elwertowski, Tom      24   1   0   0
38.   Noll, Robert          24   1   0   0
39.   Landsbert, Robin      22   1   0   0
40.   Jones, Dennis         22   0   2   0
41.   Lee, Johnny           22   1   0   0
42.   Picao, Miguel Cruz    21   0   1   1
43.   Truskier, Peter       20   1   0   0
44.   Anderson, Troy        20   1   0   0
45.   Brown, Jorg           20   0   2   0
46.   Brown, Pat            20   1   0   0
47.   Burgoyne, Nick        20   1   0   0
48.   Galway, Will          20   1   0   0
49.   Higgins, Charles      20   1   0   0
50.   Hostetter, Mat        20   1   0   0
51.   Israelson, Steve      20   1   0   0
52.   Landweber, Greg       20   1   0   0
53.   Pinkerton, Tom        20   1   0   0
54.   Studer, Thomas        20   1   0   0
55.   Davis, Gerry          19   0   1   1
56.   Nevard, John          19   0   1   1
57.   Lloyd, Jim            18   0   0   1
58.   Scheck, Andy          17   0   1   1
59.   Gundrum, Eric         15   0   1   0
60.   O'Connor, Turlough    14   0   0   2
61.   Downs, Andrew         12   0   1   0
62.   Hansgtefer, Eric      11   0   0   1
63.   Desch, Noah           10   0   1   0
64.   Barnhart, Bob         10   0   1   0
65.   Biolsi, David         10   0   1   0
66.   Braginsky, Leonid     10   0   1   0
67.   Duga, Brady           10   0   1   0
68.   Fazekas, Miklos       10   0   1   0
69.   Flowers, Sue          10   0   1   0
70.   Hewett, Kevin         10   0   1   0
71.   Hoffman, Paul         10   0   1   0
72.   McA'Nulty, Peter      10   0   1   0
73.   McKaskle, Greg        10   0   1   0
74.   Negro, Jay            10   0   1   0
75.   Panchenko, Michael    10   0   0   0
76.   Selengut, Jared       10   0   1   0
77.   Smith, Brad           10   0   1   0
78.   Strout, Joe           10   0   1   0
79.   Varilly, Patrick      10   0   1   0
80.   Waylonis, Dan         10   0   1   0
81.   Webb, Russ            10   0   1   0
82.   Zick, Aaron           10   0   1   0
83.   Zimmerman, Jordan     10   0   1   0
84.   Warner, George         8   0   0   0
85.   Bumgardner, Jim        8   0   0   0
86.   Leshner, Will          7   0   0   1
87.   Carew, Devon           7   0   0   1
88.   Coie, Robert           7   0   0   1
89.   Franklin, Ken          7   0   0   1
90.   Gogolin, Tim           7   0   0   1
91.   Hala, Ladislav         7   0   0   1
92.   Krugler, Ken           7   0   0   1
93.   Manjourides, Scott     7   0   0   1
94.   Miller, Mike           7   0   0   1
95.   Nebinger, Dave         7   0   0   1
96.   Parker, Richard        7   0   0   1
97.   Phillips, Christopher  7   0   0   1
98.   Pomakis, Keith         7   0   0   1
99.   Rufer, Russ            7   0   0   1
100.  Schlack, John          7   0   0   1
101.  Schroeder, Ulf          7   0   0   1
102.  Staw, Michael          7   0   0   1
103.  Widyatama, Yudhi       7   0   0   1

Here is Jonny's winning solution to the Area Challenge.

    Area.cp

    Copyright (c) 2002

    Jonny Taylor

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include "Area.h"
/*
   The strategy I have used requires three main data structures:
      Anchors      Represent an item in the cells[] array which initially contained a 
                  Nonzero number. Each Anchor has associated with it a (potentially 
                  large) number of...
      Shapes      Represent the position of a rectangle of the appropriate area which 
                  Overlaps its parent Anchor, but doesn't overlap any cells it shouldn't 
                  do (such as other Anchors). There is one Shape for every legal 
                  rectangle covering every Anchor. A Shape is "placed" when I know it 
                  is the only shape that can overlap its Anchor without causing fatal 
                  problems elsewhere in the grid.
      Cells         There is one MyCell structure for each cell in the problem. They track 
                  The number of Shapes that overlap them, and have the head of a 
                  linked list which includes every such overlapping Shape. This is 
                  expensive to maintain, but is crucial to the strategy I use.
                  There is also a global list which is used once all Shapes have been 
                  generated. Whenever the number of Shapes overlapping a cell drops to 
                  1, the Cell is added to this list. This is a quick way of finding such 
                  Cells when performing step 3 of the algorithm. Without this list, 
                  overall execution time increases by a factor of nearly 8 (for the test 
                  cases provided).
1.   For each anchor in turn, I discover all possible shapes. I do NOT allocate a Shape 
   structure, though - that is very time- and memory-intensive. Instead I keep track of 
   the rectangle of cells which is overlapped by ALL of the possible shapes. I know 
   that for other anchors there is no point considering shapes which overlap those 
   cells.
2.    Now I know these rectangles, I go back through the anchors considering which 
   shapes are still possible.   Hopefully this will increase the common rectangle still 
   further, reducing the number of possible shapes for the other anchors, and so on. I 
   repeat this phase until there is no significant reduction in the number of possible 
   Shapes.
3.    Now I actually generate the Shape structures and link them in to the cells which 
   they overlap
4.   With the Shape structures created, it is possible to finish off step 2 more efficently. 
   Now I maintain a list of all Anchors whose common rectangle may have been 
   altered. I work through the list and reject any shapes belonging to OTHER Anchors 
   which overlap the new common rectangle. (note that those Anchors must then be 
   added to the list). When the list becomes empty, I know that I have obtained the 
   optimal common rectangles for each Anchor.
5.   At the same time, I maintain a list of those cells which only one Shape overlaps. 
   Whenever a cell is added to that list, I can "place" that shape (which may cause 
   other cells/anchors to be added to the relevant lists for steps 4 and 5.
   
6.   Next, I experiment with placing each possible Shape in turn, and do any step 5 
   processing that this generates. During this we may end up with a cell that cannot be 
   covered by any Shape. If that is the case, I reject the original Shape that I was 
   experimenting with. This stage is extremely time-consuming. In some cases it can 
   cause the execution time to double. However, it is the only way of solving some 
   large problems within a sensible amount of time - in one case it reduced the 
   execution time from being nowhere near a solution after 30 minutes to an execution
   time of about one minute.
7.   Eventually, we will be unable to place any more shapes in this way. I then record 
   the current state, choose an Anchor, and work systematically through all possible
   Shapes that can still cover it, and repeat stage 5. If I find a cell that cannot be 
   covered by any Shape, I know there must have been a bad choice made earlier. We 
   restore the state that we just recorded, and move on to try the next possible Shape.

There are two limiting factors to this algorithm. The first is memory. Each shape that we allocate 
memory for requires just over 12 * <area> bytes. It appears that the total area of shapes 
allocated only grows slowly relative to the total area of the board. Taking into account the 
additional storage required, I would therefore expect to require a total of around 40 * <area> 
bytes of storage - i.e. 20 times the size of the input array. This seems a fairly reasonable 
requirement, making an 800x800 problem solvable, and a 200x200 problem very practical.
   
The other problem is the complexity of the problem layout. My code deals with the test cases provided 
very quickly. I also tried making bigger test cases by using the original test cases as tiles on 
a 4x4 grid, making a test case 16 times as big. It handles the largest case (800x600) in around a 
second (depending on the test machine). I then tried scaling the original test cases up by a factor 
of 2 (so that all rectangles have 4 times the area). Unfortunately it fails to get anywhere near 
solving some of the larger test cases in a reasonable amount of time. There are large areas where the 
common rectangles only cover the anchor cells themselves, leaving far too much work to be done in 
stage 6 of the algorithm.
   
   Optimizations:
      Memory pooling is a small performance gain
      Garbage lists (see Anchor::TryAllShapes) speed up the code by several times
      Maintaining the lists gCellList and gCommonRectList save a lot of unnecessary 
         scanning through arrays, and speed up the code by a factor of 10!
   
Any optimization which reduces the number of Shapes that we need to deal with will have a significant
effect. In particular, the commonRect processing sometimes takes quite a few passes for the effects 
of a change to propagate across the grid. Because this processing is cut short, more shapes are 
generated than is necessary

*/
//#define DEBUGGING
#ifdef DEBUGGING
   #define ASSERT(CONDITION)      do { if (!(CONDITION)) { Debugger(); exit(0); } } while(0)
#else
   #define ASSERT(CONDITION)      do { } while(0)
#endif
struct Shape;
struct Anchor;
struct MyCell;
struct ShapeListItem;
#define kMemPoolSize   10000000
#define kNumMemPools   100
enum
{
   kBuildCommonRect = 1,
   kRefineCommonRect,
   kGenerateShapes
};
void   NextPool(void);
Boolean   DoAutomaticPlacements(void);
void   PruneShapes(void);
Boolean   ProcessCellList(void);
long   PartitionSort(Anchor *anchorList[], long first, long last);
void   DoQuickSort(Anchor *anchorList[], long first, long last);
Anchor         *gAnchors;
MyCell         *myCells;
long         *cellsCovered;
long         *lastXInScanline, *firstXInScanline;
long         gShapeGenerationPhase;
long         gGridWidth, gGridHeight, gNumAnchors;
MyCell         *gCellList;
Anchor         *gCommonRectList;
ShapeListItem   *gCurrentGarbageList;
Boolean         gAddToCellList;
Boolean         gFailedFlag, gAbortOnFailure = false;
static char            *poolPtrs[kNumMemPools];
static char            *gMemPool = NULL;
static long            gCurrentMemPoolNum = -1;
#define CELL_COVERED(X, Y)   (cellsCovered[((Y) * gGridWidth + (X)) >> 5] & 
(1 << (((Y) * gGridWidth + (X)) & 0x1F)))

#define SET_CELL_COVERED(X, Y)   (cellsCovered[((Y) * gGridWidth + (X)) 
>> 5] |= (1 << (((Y) * gGridWidth + (X)) & 0x1F)))

#define SET_CELL_UNCOVERED(X, Y)   (cellsCovered[((Y) * gGridWidth + (X)) >> 5] ^= 
(1 << (((Y) * gGridWidth + (X)) & 0x1F)))

#define MY_CELL(X, Y)      (myCells[(Y) * gGridWidth + (X)])
#define CELL(X, Y)         (cells[(Y) * gGridWidth + (X)])
inline long MAX(long a, long b)
{
   long temp = b - a;
   ASSERT(b - (temp & (temp >> 31)) == ((a > b) ? a : b));
   return(b - (temp & (temp >> 31)));
}
inline long MIN(long a, long b)
{
   long temp = a - b;
   ASSERT(b + (temp & (temp >> 31)) == ((a > b) ? b : a));
   return(b + (temp & (temp >> 31)));
}
#define MAXIMIZE(A, B)         (A) = MAX((A), (B));
#define MINIMIZE(A, B)         (A) = MIN((A), (B));
void NextPool(void)
{
   // Move on to the next memory pool for allocation of Shape structures
   gCurrentMemPoolNum++;
   if (gCurrentMemPoolNum == kNumMemPools)
      DebugStr("\pNeed more pools");
      
   //   Check if the pool needs allocating or not. I do not bother releasing the pools after
   //   every call to Area. I do not see this as strictly a memory leak, since multiple calls
   //   to Area will not result in any more memory being allocated.
   if (poolPtrs[gCurrentMemPoolNum] == NULL)
      poolPtrs[gCurrentMemPoolNum] = (new char[kMemPoolSize]);
   gMemPool = poolPtrs[gCurrentMemPoolNum];
   if (gMemPool == NULL)
      DebugStr("\pOut of memory");
}
struct ShapeListItem
{
   Shape            *theShape;
   ShapeListItem      *next;
   ShapeListItem      *prev;
   
   ShapeListItem(void);
   void   Init(void)
   {
      theShape = NULL;
      next = this;
      prev = this;
   }
   void   AddTo(Shape *parent, ShapeListItem *listHead);
   void   Remove(void);
   Boolean   InList(void) const { return(next != this); }
};
struct MyCell
{
   long         overlapCount;
   ShapeListItem   shapeListHead;
   MyCell         *next, *prev;
   Boolean         inList;
   
         MyCell(void);
   void   MustBeCoveredBy(long index, Anchor *coveringAnchor);
   void   RemoveFromHead(void);
   void   IncrementOverlapCount(void) { overlapCount++; }
   void   AddToList(void);
   void DecrementOverlapCount(void)
   {
      ASSERT(overlapCount > 0);
      overlapCount--;
      if (overlapCount <= 1)
         AddToList();
   }
};
struct Shape
{
   Anchor            *itsAnchor;
   ShapeListItem      anchorListItem, garbageListItem;
   Shape            *nextOfAllForAnchor;
   long            top, left;
   long            width, height;
   
   void   Init(long inLeft, long inTop, long inWidth, 
                        long inHeight, Anchor *inAnchor);
   void   Reject(void);
   void   Reinstate(void);
   void   DoDecrement(void);
   ShapeListItem      cellListItems[];
};
struct Anchor
{
   long         anchorX, anchorY, area;
   long         numShapes, oneRecordSize;
   Rect         commonRect, oldCommonRect;
   ShapeListItem   shapeListHead;
   Boolean         placed, inCommonRectList;
   Anchor         *next;
   Shape         *firstOfAllShapes;
   Anchor         *nextInCommonRectList;
   
         Anchor(long inX, long inY, long inArea, Anchor *inNext);
   void   GenerateShapes(void);
   void   UpdateCommonRect(void);
   void   GenerateShapesWithWidth(long width, long firstY, 
                        long lastY);
   void   Place(void) { ASSERT(numShapes == 1); Place(shapeListHead.next->theShape); }
   void   Place(Shape *theShape);
   Boolean TryAllShapes(void);
   static int CompareAnchorsBySize(const void *a1, 
            const void *a2);
};
MyCell
MyCell::MyCell(void)
{
   overlapCount = 0;
   next = prev = NULL;
   inList = false;
}
void MyCell::MustBeCoveredBy(long index, Anchor *coveringAnchor)
{
   // Called when we know that the cell can only be covered by a shape based on the 
   // specified anchor
   // (i.e. the cell is included in the anchor's commonRect
   cellsCovered[index >> 5] |= (1 << (index & 0x1F));
   
   // Any shapes that overlap this cell which are not based on this anchor can be 
   // rejected
   for (ShapeListItem *shapeItem = shapeListHead.next; 
                  shapeItem->theShape != NULL; )
   {
      ShapeListItem   *nextShapeItem = shapeItem->next;
      if (shapeItem->theShape->itsAnchor != coveringAnchor)
      {
         shapeItem->theShape->Reject();
         if (!shapeItem->theShape->itsAnchor->inCommonRectList)
         {
            // Add the anchor to the list of ones whose commonRect needs updating
            shapeItem->theShape->itsAnchor->nextInCommonRectList = 
                           gCommonRectList;
            gCommonRectList = shapeItem->theShape->itsAnchor;
            gCommonRectList->inCommonRectList = true;
         }
      }
      shapeItem = nextShapeItem;
   }
}
void MyCell::RemoveFromHead(void)
{
   // Remove this cell from the head of gCellList
   ASSERT(inList);
   ASSERT(prev == NULL);
   if (next != NULL)
      next->prev = NULL;
   gCellList = next;
   next = NULL;
   prev = NULL;
   inList = false;
}
void MyCell::AddToList(void)
{
   // Add this cell to the list of ones which only have one Shape overlapping them
   if ((gAddToCellList) &&
      (!inList))
   {
      ASSERT(next == NULL);
      ASSERT(prev == NULL);
      ASSERT(gCellList != this);
      
      next = gCellList;
      if (next != NULL)
         next->prev = this;
      prev = NULL;
      gCellList = this;
      inList = true;
   }
   
   //   Setting this flag will save us from doing unnecessary work when we have already 
   //   got  a cell which cannot be covered by any Shape at all
   if (overlapCount == 0)
      gFailedFlag = true;
}
ShapeListItem 
ShapeListItem::ShapeListItem(void)
{
   theShape = NULL;
   next = this;
   prev = this;
}
void ShapeListItem::AddTo(Shape *parent, ShapeListItem *listHead)
{
   ASSERT(!InList());
   theShape = parent;
   ShapeListItem *theNext = listHead->next;
   next = theNext;
   listHead->next = this;
   prev = listHead;
   theNext->prev = this;
}
void ShapeListItem::Remove(void)
{
   ASSERT(InList());
   ShapeListItem *theNext = next;
   ShapeListItem *thePrev = prev;
   thePrev->next = theNext;
   theNext->prev = thePrev;
   next = this;
}
Shape
void Shape::Init(long inLeft, long inTop, long inWidth, long inHeight, Anchor *inAnchor)
{
   long   i = 0;
   
   left = inLeft;
   top = inTop;
   width = inWidth;
   height = inHeight;
   itsAnchor = inAnchor;
   nextOfAllForAnchor = inAnchor->firstOfAllShapes;
   inAnchor->firstOfAllShapes = this;
   anchorListItem.Init();
   garbageListItem.Init();
   for (i = width * height - 1; i >= 0 ; i--)
      cellListItems[i].Init();
   
   // Link to its parent anchor
   Reinstate();
}
void Shape::Reject(void)
{
   // Don't bother doing this if this shape layout had already been found not to work
   if (gAbortOnFailure && gFailedFlag)
      return;
   // Remove this shape from every cell that it is linked to. Loop is unrolled for slight
   // performance increase
   for (long y = top, i = 0; y < top + height; y++)
   {
      MyCell   *theCell;
      long   x;
      for (x = left, theCell = &MY_CELL(x, y);
            x < left + width;
            x++, i++, theCell++)
      {
         theCell->DecrementOverlapCount();   
         cellListItems[i].Remove();
         
         x++; i++; theCell++;
         if (x == left + width)
            break;
         theCell->DecrementOverlapCount();   
         cellListItems[i].Remove();
         
         x++; i++; theCell++;
         if (x == left + width)
            break;
         theCell->DecrementOverlapCount();   
         cellListItems[i].Remove();
      }
   }
   
   // Remove it from its owning Anchor
   anchorListItem.Remove();
   ASSERT(itsAnchor->numShapes > 0);
   itsAnchor->numShapes--;
   
   // Add it to the garbage list
   if (gCurrentGarbageList != NULL)
      garbageListItem.AddTo(this, gCurrentGarbageList);
}
void Shape::Reinstate(void)
{
   // This shape is now a valid possibility again
   // Link to its parent anchor
   anchorListItem.AddTo(this, &itsAnchor->shapeListHead);
   itsAnchor->numShapes++;
   itsAnchor->placed = false;
   
   // Link into the cells which it overlaps
   for (long y = top, i = 0; y < top + height; y++)
   {
      MyCell   *theCell;
      long   x;
      for (x = left, theCell = &MY_CELL(x, y);
            x < left + width;
            x++, i++, theCell++)
      {
         theCell->IncrementOverlapCount();
         cellListItems[i].AddTo(this, &theCell->shapeListHead);
      }
   }
}
Anchor
Anchor::Anchor(long inX, long inY, long inArea, Anchor *inNext)
{
   anchorX = inX;
   anchorY = inY;
   area = inArea;
   next = inNext;
   numShapes = 0;
   placed = false;
   gNumAnchors++;
   firstOfAllShapes = NULL;
   inCommonRectList = false;
   
   SET_CELL_COVERED(anchorX, anchorY);
   oneRecordSize = (sizeof(Shape) + area * sizeof(ShapeListItem)) + 4;
   oneRecordSize -= oneRecordSize % 4;
}
void Anchor::GenerateShapes(void)
{
   long         firstX, firstY, lastX, lastY, x, y;
   
   if (gShapeGenerationPhase != kBuildCommonRect)
   {
      // We need to unmark the cells in commonRect while in this function
      for (y = commonRect.top; y <= commonRect.bottom; y++)
         for (x = commonRect.left; x <= commonRect.right; x++)
         {
            long index = y * gGridWidth + x;
            cellsCovered[index >> 5] &= ~(1 << (index & 0x1F));
         }
   }
   SetRect(&commonRect, 0, 0, 32767, 32767);
   
   // Find the min/max y position for shapes
   firstY = MAX(anchorY - area + 1, 0);
   for (y = anchorY - 1; y >= firstY; y--)
      if (CELL_COVERED(anchorX, y))
      {
         firstY = y + 1;
         break;
      }
   lastY = MIN(anchorY + area, gGridHeight) - 1;
   for (y = anchorY + 1; y <= lastY; y++)
      if (CELL_COVERED(anchorX, y))
      {
         lastY = y - 1;
         break;
      }
   
   // Scan out from this centre line row by row, obtaining a series of coordinates 
   // defining a convex area centred on the anchor cell - those cells which can be 
   // occupied by a shape overlapping the anchor cell
   firstX = MAX(0, anchorX - area + 1);
   lastX = MIN(gGridWidth, anchorX + area) - 1;
   for (y = anchorY; y >= firstY; y--)
   {
      // To speed this loop up, I avoid reloading cellsCovered when we are reading 
      // from the same long several times in succession
      unsigned long theMask = 
               (1 << ((y * gGridWidth + anchorX - 1) & 0x1F));
      unsigned long theIndex = (y * gGridWidth + anchorX - 1) >> 5;
      for (x = anchorX - 1; x >= firstX; x--)
      {
         if (cellsCovered[theIndex] & theMask)
            ASSERT(CELL_COVERED(x, y));
         else
            ASSERT(!CELL_COVERED(x, y));
            
         if (cellsCovered[theIndex] & theMask)
         {
            firstX = x + 1;
            break;
         }
         theMask = theMask >> 1;
         if (theMask == 0)
         {
            theMask = 0x80000000;
            theIndex--;
         }
      }
      firstXInScanline[y] = firstX;
      theMask = (1 << ((y * gGridWidth + anchorX + 1) & 0x1F));
      theIndex = (y * gGridWidth + anchorX + 1) >> 5;
      for (x = anchorX + 1; x <= lastX; x++)
      {
         if (cellsCovered[theIndex] & theMask)
            ASSERT(CELL_COVERED(x, y));
         else
            ASSERT(!CELL_COVERED(x, y));
         if (cellsCovered[theIndex] & theMask)
         {
            lastX = x - 1;
            break;
         }
         theMask = theMask << 1;
         if (theMask == 0)
         {
            theMask = 0x00000001;
            theIndex++;
         }
      }
      lastXInScanline[y] = lastX;
   }
   firstX = firstXInScanline[anchorY];
   lastX = lastXInScanline[anchorY];   
   for (y = anchorY + 1; y <= lastY; y++)
   {
      // There is no reason not to do the same optimization as above (using theMask 
      //   and theIndex)
      // - I must have just forgotten to do it
      for (x = anchorX - 1; x >= firstX; x--)
      {
         if (CELL_COVERED(x, y))
         {
            firstX = x + 1;
            break;
         }
      }
      firstXInScanline[y] = firstX;
      for (x = anchorX + 1; x <= lastX; x++)
      {
         if (CELL_COVERED(x, y))
         {
            lastX = x - 1;
            break;
         }
      }
      lastXInScanline[y] = lastX;
   }
   GenerateShapesWithWidth(1, firstY, lastY);
   if (area != 1)
      GenerateShapesWithWidth(area, firstY, lastY);
   // Nothing clever here - just try all possible widths to see if they result in an integer 
   //   height
   for (long width = 2; width <= area / 2; width++)
      if ((area % width) == 0)
         GenerateShapesWithWidth(width, firstY, lastY);
   ASSERT((gShapeGenerationPhase != kGenerateShapes) || (numShapes > 0));
   if ((numShapes == 1) &&
      (gShapeGenerationPhase == kGenerateShapes))
   {
      // There is only one shape possible that covers this anchor, so place it 
      //   immediately
      Place();
   }
   else
   {
      // Fill in the anchor pointer for the cells that will be covered by every
      // possible shape
      // Note that the right/bottom values for the rectangle give the first cell NOT 
      //   enclosed
      for (y = commonRect.top; y <= commonRect.bottom; y++)
         for (x = commonRect.left; x <= commonRect.right; x++)
            MY_CELL(x, y).MustBeCoveredBy(y * gGridWidth + x, this);
   }
}
void Anchor::GenerateShapesWithWidth(long width, long firstY, long lastY)
{
   long   x, y;
   long   height = area / width;
   // Now we have generated the scanlines showing which cells are free, generate the.
   // shapes   We only need to consider the top and bottom scanlines that each shape 
   // overlaps, due to the convex nature of the area enclosed by the scanlines
   firstY = MAX(firstY, anchorY - height + 1);
   lastY = lastY - height + 1;
   lastY = MIN(lastY, anchorY);
   for (y = firstY; y <= lastY; y++)
   {
      ASSERT(firstXInScanline[y] != -1);
      ASSERT(lastXInScanline[y] != -1);
      ASSERT(firstXInScanline[y + height - 1] != -1);
      ASSERT(lastXInScanline[y + height - 1] != -1);
      long   firstX = firstXInScanline[y];
      MAXIMIZE(firstX, MAX(firstXInScanline[y + height - 1], 
                  anchorX - width + 1));
      long   lastX = lastXInScanline[y];
      MINIMIZE(lastX, lastXInScanline[y + height - 1]);
      lastX = lastX - width + 1;
      MINIMIZE(lastX, anchorX);
      if (firstX > lastX)
         continue;
      // Keep track of the area which all shapes overlap
      MAXIMIZE(commonRect.top, y);
      MINIMIZE(commonRect.bottom, y + height - 1);
      MAXIMIZE(commonRect.left, lastX);
      MINIMIZE(commonRect.right, firstX + width - 1);
      if (gShapeGenerationPhase == kGenerateShapes)
      {
         // Create the Shape records
         for (x = firstX; x <= lastX; x++)
         {
            if (((char*)gMemPool) + oneRecordSize - 
                  (char*)poolPtrs[gCurrentMemPoolNum] > kMemPoolSize)
            {
               // Need more memory
               NextPool();
            }
            ((Shape*)gMemPool)->Init(x, y, width, height, this);
            gMemPool += oneRecordSize;
         }
      }
   }
}
void Anchor::Place(Shape * shapeToPlace)
{
   // Settle on a final position for this anchor
   ASSERT(!placed);
   placed = true;
   
   if (numShapes > 1)
   {
      // Remove the other shapes for this anchor - they will not now be used
      for (ShapeListItem *shapeItem = shapeListHead.next; 
                     shapeItem->theShape != NULL; )
      {
         ShapeListItem   *nextShapeItem = shapeItem->next;
         if (shapeItem->theShape != shapeToPlace)
         {
            shapeItem->theShape->Reject();
         }
         shapeItem = nextShapeItem;
      }
   }
   
   ASSERT(numShapes == 1);
   // Fill in the anchor pointer for the cells that will be covered by the shape
   for (long y = shapeToPlace->top; 
               y < shapeToPlace->top + shapeToPlace->height; y++)
      for (long x = shapeToPlace->left; 
                  x < shapeToPlace->left + shapeToPlace->width; x++)
      {
         MyCell *theCell = &MY_CELL(x, y);
         theCell->MustBeCoveredBy(y * gGridWidth + x, this);
      }
}
Boolean Anchor::TryAllShapes(void)
{
   /*   This function is called when all logical methods have been tried. It just uses brute 
      force.  It tries placing all possible shapes that will cover this anchor one after 
      the other. It considers all the repercussions of placing that shape (recursing via 
      the call to DoAutomaticPlacements if necessary). The conclusion will either be 
      that all cells could be covered (success) or that we failed - in which case we 
      know that some previous placement that was made must have been incorrect.
      
      If a given placement doesn't work, we need to restore the initial state so we can 
      try the next placement. To speed this up, we do not forget about rejected shapes - 
      we add them to the global garbage list. When restoring, we reinstate any shapes 
      in that garbage list.
      Note that I don't bother to restore the cellsCovered bitmap - that is not needed by 
      the time we get to this stage   */
      
   ShapeListItem   *oldGarbageList = gCurrentGarbageList;
   ShapeListItem   localGarbageList;
   MyCell         *theCell;
   gCurrentGarbageList = &localGarbageList;
   // Work through all shapes. The anchor keeps a list of all shapes that are based 
   // around it. Unfortunately the order of the list changes as shapes are removed and 
   // reinstated. As a result, we can't iterate through that list, and have to use the list of 
   //   all the shapes that were ever created for the anchor.
   // This could be speeded up by removing from the list any shapes that have 
   //   DEFINITELY been rejected for good.
   for (Shape *theShape = firstOfAllShapes; theShape != NULL; 
                  theShape = theShape->nextOfAllForAnchor)
   {
      if (!theShape->anchorListItem.InList())
         continue;
      ASSERT(gCellList == NULL);
      Place(theShape);
      
      if (DoAutomaticPlacements())
         return(true);
      
      // Failed - restore current state
      while (localGarbageList.next != &localGarbageList)
      {
         ShapeListItem *theShapeToReinstate = localGarbageList.next;
         theShapeToReinstate->Remove();
         theShapeToReinstate->theShape->Reinstate();
      }
      // Although gCellList may not be empty, it should not contain any entries we 
      // need to do any work for      
      while (gCellList != NULL)
      {
         theCell = gCellList;
         ASSERT(theCell->overlapCount > 1);
         theCell->RemoveFromHead();
      }
   }
   // If we get here then we have tried and failed with every possible shape to cover the 
   //   anchor. Return failure
   gCurrentGarbageList = oldGarbageList;
   return(false);
}
void Anchor::UpdateCommonRect(void)
{
   /*   This function scans through all the Anchor's Shapes to recalculate commonRect. 
      Note that the calls to MustBeCoveredBy may call Reject for other anchors' 
      shapes, causing those anchors to require a call to this function. We don't call it 
      immediately, though. This would lead to enormous recursion and I think would 
      result in more calls to this function than are strictly necessary                */
   Rect   newCommonRect = {0, 0, 32767, 32767};
   
   ASSERT(gCommonRectList == this);
   ASSERT(inCommonRectList);
   gCommonRectList = gCommonRectList->nextInCommonRectList;
   inCommonRectList = false;
   for (ShapeListItem *shapeItem = shapeListHead.next; 
            shapeItem->theShape != NULL; shapeItem = shapeItem->next)
   {
      Shape *theShape = shapeItem->theShape;
      
      MAXIMIZE(newCommonRect.left, theShape->left);
      MAXIMIZE(newCommonRect.top, theShape->top);
      MINIMIZE(newCommonRect.right, theShape->left + 
               theShape->width - 1);
      MINIMIZE(newCommonRect.bottom, theShape->top + 
               theShape->height - 1);
   }
   //   For any cells included in newCommonRect but not in commonRect, reject any 
   //   other shapes overlapping
   //   that cell, and mark their anchors for update.
   long x, y;
   for (y = newCommonRect.top; y < commonRect.top; y++)
      for (x = newCommonRect.left; x <= newCommonRect.right; x++)
         MY_CELL(x, y).MustBeCoveredBy(y * gGridWidth + x, this);
   for (y = commonRect.bottom + 1; y <= newCommonRect.bottom; y++)
      for (x = newCommonRect.left; x <= newCommonRect.right; x++)
         MY_CELL(x, y).MustBeCoveredBy(y * gGridWidth + x, this);
   for (x = newCommonRect.left; x < commonRect.left; x++)
      for (y = commonRect.top; y <= commonRect.bottom; y++)
         MY_CELL(x, y).MustBeCoveredBy(y * gGridWidth + x, this);
   for (x = commonRect.right + 1; x <= newCommonRect.right; x++)
      for (y = commonRect.top; y <= commonRect.bottom; y++)
         MY_CELL(x, y).MustBeCoveredBy(y * gGridWidth + x, this);
   commonRect = newCommonRect;
}
int Anchor::CompareAnchorsBySize(const void *a1, const void *a2)
{
   return((*(Anchor**)a1)->area - (*(Anchor**)a2)->area);
}
DoAutomaticPlacements
Boolean DoAutomaticPlacements(void)
{
   // Starting from the current state, make any placements that have to be made.
   // This means checking for Cells that only one remaining shape overlaps.
   // Note that there is no point for checking separately for anchors that only
   // have one valid shape left - that is covered by the Cell condition.
   if (!ProcessCellList())
      return(false);
   // If there is an unplaced anchor, try each possible shape that will cover it
   // The algorithm might be improved by processing the anchors in a specific order
   for (Anchor *anchor = gAnchors; anchor != NULL; 
                  anchor = anchor->next)
   {
      if (!anchor->placed)
         return(anchor->TryAllShapes());
   }
   // If we get here then we have solved the problem
   return(true);
}
PruneShapes
void PruneShapes(void)
{
   /*   This function is very similar to Anchor::TryAllShapes. The difference is that it 
      doesn't recurse.
      The simple checks done so far haven't eliminated some of the shapes. There may 
      be quite a few remaining which cannot actually be placed without causing some 
      cells to be uncoverable. This function eliminates those shapes. It is by far the 
      slowest routine in the algorithm. In most small test cases it leads to a longer 
      running time than if we just skipped this stage (in a few cases it nearly doubles 
      it). However, in cases where there are large open expanses with lots of shapes 
      that could cover them, it is crucial (without it no solution is found in a reasonable 
      amount of time). Since I can't be sure of spotting such cases in advance, I am 
      forced to call this routine unconditionally   */
   ShapeListItem   *oldGarbageList = gCurrentGarbageList;
   ShapeListItem   localGarbageList;
   Anchor         *anchor;
   
   gCurrentGarbageList = &localGarbageList;
   for (anchor = gAnchors; anchor != NULL; anchor = anchor->next)
   {
      if (anchor->numShapes <= 1)
         continue;
      // Work through all shapes. The anchor keeps a list of all shapes that are based 
      // around it. Unfortunately the order of the list changes as shapes are removed and 
      // reinstated. As a result, we can't iterate through that list, and have to use the list 
      //   of all the shapes that were ever created for the anchor
      for (Shape *theShape = anchor->firstOfAllShapes; 
                     theShape != NULL; 
                     theShape = theShape->nextOfAllForAnchor)
      {
         if (!theShape->anchorListItem.InList())
            continue;
         ASSERT(gCellList == NULL);
         anchor->Place(theShape);
         if (!ProcessCellList())
         {
            // This shape will cause contradictions. Reject it for good.
            theShape->Reject();
            theShape->garbageListItem.Remove();
         }
         // Restore current state
         while (localGarbageList.next != &localGarbageList)
         {
            ShapeListItem *theShapeToReinstate = localGarbageList.next;
            theShapeToReinstate->Remove();
            theShapeToReinstate->theShape->Reinstate();
         }
         //   Note that unlike in Anchor::TryAllShapes there may be genuine work
         //   to do with the cell-list, because we may have rejected theShape for good
         ProcessCellList();
      }
      if (anchor->numShapes == 1)
         anchor->Place();
      ProcessCellList();
   }
   gCurrentGarbageList = oldGarbageList;
}
ProcessCellList
Boolean ProcessCellList(void)
{
   gAbortOnFailure = true;
   gFailedFlag = false;
   
   while (gCellList != NULL)
   {
      MyCell *theCell = gCellList;
      if (theCell->overlapCount == 0)
      {
         // This round has failed because theCell cannot be covered by any remaining 
         //   Shapes
         gAbortOnFailure = false;
         return(false);
      }
      theCell->RemoveFromHead();
      if (theCell->overlapCount > 1)
         continue;
      Shape *theShape = theCell->shapeListHead.next->theShape;
      if (theShape->itsAnchor->placed)
         continue;
      ASSERT(theCell->overlapCount == 1);
      theShape->itsAnchor->Place(theShape);
      if (gFailedFlag == true)
      {
         gAbortOnFailure = false;
         return(false);
      }
   }
   gAbortOnFailure = false;
   return(true);
}
DoQuickSort
void DoQuickSort(Anchor *anchorList[], long first, long last)
{
   if(first < last)
   {
      long   mid = PartitionSort(anchorList, first, last);
      DoQuickSort(anchorList, first, mid);
      DoQuickSort(anchorList, mid + 1, last);
   }
}
PartitionSort
long PartitionSort(Anchor *anchorList[], long first, long last)
{
   long          itemIndex = first;
   long         ii=first-1,
               jj=last+1;
   
   while(1)
   {
      do {   jj--;   } while ((anchorList[jj]->area - 
                                 anchorList[itemIndex]->area) > 0);
      do {   ii++;   } while ((anchorList[ii]->area - 
                                 anchorList[itemIndex]->area) < 0);
      if (ii < jj)
      {
         Anchor   *temp = anchorList[ii];
         anchorList[ii] = anchorList[jj];
         anchorList[jj] = temp;
      }
      else
      {
         return(jj);
      }
   }
}
Area
void Area(
   short *cells,
   /* index by [row*rectWidth + col[ */
   short rectWidth,
   short rectHeight,
   Rect yourRects[]
)
{
   long         x, y;
   Anchor         *anchor;
   Shape         *theShape;
   Anchor         **anchorList;
   // Initialize the memory pool if this is the first time we have been called
   if (gCurrentMemPoolNum == -1)
   {
      for (long poolIndex = 0; poolIndex < kNumMemPools; 
                     poolIndex++)
         poolPtrs[poolIndex] = NULL;
      NextPool();
   }
   myCells = new MyCell[rectWidth * rectHeight];
   if (myCells == NULL)
      DebugStr("\pOut of memory");
   // Allocate a bitmap indicating which cells are covered by a Shape that has been 
   //   placed already
   cellsCovered = new long[(rectWidth * rectHeight) / 32 + 1];
   if (cellsCovered == NULL)
      DebugStr("\pOut of memory");
   memset(cellsCovered, 0, 
            (4 * ((rectWidth * rectHeight) / 32 + 1)));
   
   lastXInScanline = new long[rectHeight];
   firstXInScanline = new long[rectHeight];
   if (lastXInScanline == NULL)
      DebugStr("\pOut of memory");
   if (firstXInScanline == NULL)
      DebugStr("\pOut of memory");
   gGridWidth = rectWidth;
   gGridHeight = rectHeight;
   gCurrentGarbageList = NULL;
   gAnchors = NULL;
   gNumAnchors = 0;
   gAddToCellList = false;
   gCellList = NULL;
   gCommonRectList = NULL;
   anchorList = new Anchor*[rectWidth * rectHeight];
   if (anchorList == NULL)
      DebugStr("\pOut of memory");
   long i = 0;
   // Create the Anchors
   for (x = 0; x < rectWidth; x++)
      for (y = 0; y < rectHeight; y++)
         if (CELL(x, y) != 0)
         {
            anchorList[i] = gAnchors = 
                        new Anchor(x, y, CELL(x, y), gAnchors);
            if (anchorList[i] == NULL)
               DebugStr("\pOut of memory");
            i++;
         }
   ASSERT(i == gNumAnchors);
   /*   It seems generally to be worth generating the shapes starting with the largest-area 
      anchor.  Tests with random distributions of anchor cells for a range of rectangle
      layouts show that the time taken is 20-80% that taken if the anchors are processed
      in the order they were found. However in a few cases performance is worse (may
      take 200% of the time). This generally happens where the largest-area anchor is 
      in an unconstrained space significantly bigger than its area (so there are many 
      possible shapes it could take). A more sophisticated solution might be able to spot 
      such unconstrained areas and try to shrink them by processing the surrounding 
      anchors first.
      Generating the shapes is very memory- and time-consuming. On the first few 
      passes I don't actually allocate the Shape structures - I just keep track of each 
      anchor's commonRect. This reduces the number of shapes that I actually need to 
      generate on the final pass. In some cases it doesn't have much effect, but in others 
      it may reduce the number of shapes by a factor of 10 or more.   */
   DoQuickSort(anchorList, 0, gNumAnchors - 1);
   gShapeGenerationPhase = kBuildCommonRect;
   for (i = gNumAnchors - 1; i >= 0; i--)
      anchorList[i]->GenerateShapes();
   gShapeGenerationPhase = kRefineCommonRect;
   for (long iter = 0; iter < 4; iter++)
      for (i = gNumAnchors - 1; i >= 0; i--)
         anchorList[i]->GenerateShapes();
   
   gShapeGenerationPhase = kGenerateShapes;
   for (i = gNumAnchors - 1; i >= 0; i--)
      anchorList[i]->GenerateShapes();
   // Look for any cells that only have one shape overlapping then - and place that 
   //   shape
   ASSERT(gCellList == NULL);
   gCellList = NULL;
   gAddToCellList = true;
   for (x = 0; x < gGridWidth; x++)
      for (y = 0; y < gGridHeight; y++)
      {
         MyCell *theCell = &MY_CELL(x, y);
         ASSERT(theCell->overlapCount != 0);
         if (theCell->overlapCount == 1)
         {
            theShape = theCell->shapeListHead.next->theShape;
            if (!theShape->itsAnchor->placed)
               theShape->itsAnchor->Place(theShape);
         }
      }
   //   Update the commonRect for each anchor in turn, propagating to other anchors as 
   //   appropriate.
   while (gCommonRectList != NULL)
   {
      gCommonRectList->UpdateCommonRect();
      ProcessCellList();
   }
   
   //   Work though every shape for every anchor. Try placing it, and if that leads to a 
   //   contradiction,
   //   reject that shape
   PruneShapes();
   
   while (gCommonRectList != NULL)
   {
      gCommonRectList->UpdateCommonRect();
      ProcessCellList();
   }
   
   //   Logic can do no more for us. Use brute force to finish it off
   if (!DoAutomaticPlacements())
   {
      printf("Failed to find a solution\n");
      memset(yourRects, 0, gNumAnchors * sizeof(Rect));
      return;
   }
   // When we get here we should have solved the problem
   long   numRects = 0;
   for (anchor = gAnchors; anchor != NULL; numRects++)
   {
      Anchor   *nextAnchor = anchor->next;
      ASSERT(anchor->placed);
      theShape = anchor->shapeListHead.next->theShape;
      yourRects[numRects].left = theShape->left;
      yourRects[numRects].top = theShape->top;
      yourRects[numRects].right = theShape->left + theShape->width;
      yourRects[numRects].bottom = theShape->top + theShape->height;
      delete anchor;
      anchor = nextAnchor;
   }
   
   delete[] myCells;
   delete[] cellsCovered;
   delete[] anchorList;
   delete[] lastXInScanline;
   delete[] firstXInScanline;
   gMemPool = poolPtrs[0];
   gCurrentMemPoolNum = 0;
}

Bob Boonstra

 
AAPL
$104.75
Apple Inc.
+1.76
MSFT
$44.97
Microsoft Corpora
+0.59
GOOG
$543.81
Google Inc.
+11.10

MacTech Search:
Community Search:

Software Updates via MacUpdate

Art Text 2.4.8 - Create high quality hea...
Art Text is an OS X application for creating high quality textual graphics, headings, logos, icons, Web site elements, and buttons. Thanks to multi-layer support, creating complex graphics is no... Read more
Live Interior 3D Pro 2.9.6 - Powerful an...
Live Interior 3D Pro is a powerful yet very intuitive interior designing application. View Video Tutorials It has every feature of Live Interior 3D Standard, plus some exclusive ones: Create multi... Read more
The Hit List 1.1.7 - Advanced reminder a...
The Hit List manages the daily chaos of your modern life. It's easy to learn - it's as easy as making lists. And it's powerful enough to let you plan, then forget, then act when the time is right.... Read more
jAlbum Pro 12.2.4 - Organize your digita...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code!... Read more
jAlbum 12.2.4 - Create custom photo gall...
With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly, with pro results Simply drag and drop photos into groups, choose a design... Read more
ExpanDrive 4.1.7 - Access remote files o...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
OmniOutliner Pro 4.1.3 - Pro version of...
OmniOutliner Pro is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It'... Read more
Evernote 5.6.2 - Create searchable notes...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
OmniOutliner 4.1.3 - Organize your ideas...
OmniOutliner is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more
BBEdit 11.0 - Powerful text and HTML edi...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more

Latest Forum Discussions

See All

Puzzle to the Center of the Earth Review
Puzzle to the Center of the Earth Review By Campbell Bird on October 23rd, 2014 Our Rating: :: SPELUNKING PUZZLESUniversal App - Designed for iPhone and iPad Do some puzzles to make some platforms in this smart and fun free-to-play... | Read more »
Sleep Attack TD Review
Sleep Attack TD Review By Jennifer Allen on October 23rd, 2014 Our Rating: :: A TRUE TWISTUniversal App - Designed for iPhone and iPad Sleep Attack TD is a tower defense game with a difference – you can rotate the layout – and it’s... | Read more »
Mecanic (Education)
Mecanic 1.0 Device: iOS Universal Category: Education Price: $1.99, Version: 1.0 (iTunes) Description: Plates, screws, wheels ... Everything you need to achieve whatever you want... MECHANICWith 'MECANIC' kids will have fun... | Read more »
Earn Your Master Camper Badge in Camp Po...
Earn Your Master Camper Badge in Camp Pokemon Posted by Jessica Fisher on October 23rd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Garruk Gets His Revenge in a New Magic 2...
Garruk Gets His Revenge in a New Magic 2015 Expansion, Coming This November Posted by Jessica Fisher on October 23rd, 2014 [ permalink ] | Read more »
Sentinels of the Multiverse Review
Sentinels of the Multiverse Review By Rob Thomas on October 23rd, 2014 Our Rating: :: SENTINELS ASSEMBLEiPad Only App - Designed for the iPad Greater Than Games’ tabletop classic, Sentinels of the Multiverse swoops in to save the... | Read more »
Build Your Own Fantasy Football Dynasty...
Build Your Own Fantasy Football Dynasty with Draft Day Posted by Jessica Fisher on October 23rd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Cars: Fast as Lightning – Tips, Tricks,...
Hey there, Stickers: Want to know all about how impressed we were with Radiator Springs? Check out our Cars: Fast as Lightning review! Cars: Fast as Lightning is a cute and fun app that combines racing and town-building with the charisma and... | Read more »
Jam Messenger Review
Jam Messenger Review By Jennifer Allen on October 23rd, 2014 Our Rating: :: SIMPLE MESSAGINGiPhone App - Designed for the iPhone, compatible with the iPad Want a very quick way to send push-based messages? Jam Messenger is basic... | Read more »
Felllice (Games)
Felllice 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: EXCLUSIVE PRICE DROP! 50% OFF FOR A LIMITED TIME! EAT EAT EAT AND GROW ! | Read more »

Price Scanner via MacPrices.net

Save up to $125 on Retina MacBook Pros
B&H Photo has the new 2014 13″ and 15″ Retina MacBook Pros on sale for up to $125 off MSRP. Shipping is free, and B&H charges NY sales tax only. They’ll also include free copies of Parallels... Read more
Apple refurbished Time Capsules available sta...
The Apple Store has certified refurbished Time Capsules available for up to $60 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $255... Read more
Textilus New Word, Notes and PDF Processor fo...
Textilus is new word-crunching, notes, and PDF processor designed exclusively for the iPad. I haven’t had time to thoroughly check it out yet, but it looks great and early reviews are positive.... Read more
WD My Passport Pro Bus-Powered Thunderbolt RA...
WD’s My Passport Pro RAID solution is powered by an integrated Thunderbolt cable for true portability and speeds as high as 233 MB/s. HighlightsOverviewSpecifications Transfer, Back Up And Edit In... Read more
Save with Best Buy’s College Student Deals
Take an additional $50 off all MacBooks and iMacs at Best Buy Online with their College Students Deals Savings, valid through November 1st. Anyone with a valid .EDU email address can take advantage... Read more
iPad Air 2 & iPad mini 3 Best Tablets Yet...
The new iPads turned out to be pretty much everything I’d been hoping for and more than I’d expected.”More” particularly in terms of a drinking-from-a-firehose choice of models and configurations,... Read more
Drafts 4 Reinvents iOS Productivity App
N Richland Hills, Texas based Agile Tortoise has announced the release of Drafts 4 for iPhone and iPad. Drafts is a quick capture note taking app with flexible output actions. Drafts 4 scales from... Read more
AT&T accepting preorders for new iPads fo...
AT&T Wireless is accepting preorders for the new iPad Air 2 and iPad mini 3, cellular models, for $100 off MSRP with a 2-year service agreement: - 16GB iPad Air 2 WiFi + Cellular: $529.99 - 64GB... Read more
Apple offering refurbished Mac Pros for up to...
The Apple Store is offering Apple Certified Refurbished 2013 Mac Pros for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The... Read more
Select MacBook Airs $100 off MSRP, free shipp...
B&H Photo has 2014 a couple of MacBook Airs on sale for $100 off MSRP. Shipping is free, and B&H charges NY sales tax only. They also include free copies of Parallels Desktop and LoJack for... Read more

Jobs Board

Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Position Opening at *Apple* - Apple (United...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.