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

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Latest Forum Discussions

See All

Whitethorn Games combines two completely...
If you have ever gone fishing then you know that it is a lesson in patience, sitting around waiting for a bite that may never come. Well, that's because you have been doing it wrong, since as Whitehorn Games now demonstrates in new release Skate... | Read more »
Call of Duty Warzone is a Waiting Simula...
It's always fun when a splashy multiplayer game comes to mobile because they are few and far between, so I was excited to see the notification about Call of Duty: Warzone Mobile (finally) launching last week and wanted to try it out. As someone who... | Read more »
Albion Online introduces some massive ne...
Sandbox Interactive has announced an upcoming update to its flagship MMORPG Albion Online, containing massive updates to its existing guild Vs guild systems. Someone clearly rewatched the Helms Deep battle in Lord of the Rings and spent the next... | Read more »
Chucklefish announces launch date of the...
Chucklefish, the indie London-based team we probably all know from developing Terraria or their stint publishing Stardew Valley, has revealed the mobile release date for roguelike deck-builder Wildfrost. Developed by Gaziter and Deadpan Games, the... | Read more »
Netmarble opens pre-registration for act...
It has been close to three years since Netmarble announced they would be adapting the smash series Solo Leveling into a video game, and at last, they have announced the opening of pre-orders for Solo Leveling: Arise. [Read more] | Read more »
PUBG Mobile celebrates sixth anniversary...
For the past six years, PUBG Mobile has been one of the most popular shooters you can play in the palm of your hand, and Krafton is celebrating this milestone and many years of ups by teaming up with hit music man JVKE to create a special song for... | Read more »
ASTRA: Knights of Veda refuse to pump th...
In perhaps the most recent example of being incredibly eager, ASTRA: Knights of Veda has dropped its second collaboration with South Korean boyband Seventeen, named so as it consists of exactly thirteen members and a video collaboration with Lee... | Read more »
Collect all your cats and caterpillars a...
If you are growing tired of trying to build a town with your phone by using it as a tiny, ineffectual shover then fear no longer, as Independent Arts Software has announced the upcoming release of Construction Simulator 4, from the critically... | Read more »
Backbone complete its lineup of 2nd Gene...
With all the ports of big AAA games that have been coming to mobile, it is becoming more convenient than ever to own a good controller, and to help with this Backbone has announced the completion of their 2nd generation product lineup with their... | Read more »
Zenless Zone Zero opens entries for its...
miHoYo, aka HoYoverse, has become such a big name in mobile gaming that it's hard to believe that arguably their flagship title, Genshin Impact, is only three and a half years old. Now, they continue the road to the next title in their world, with... | Read more »

Price Scanner via MacPrices.net

Deal Alert! B&H Photo has Apple’s 14-inch...
B&H Photo has new Gray and Black 14″ M3, M3 Pro, and M3 Max MacBook Pros on sale for $200-$300 off MSRP, starting at only $1399. B&H offers free 1-2 day delivery to most US addresses: – 14″ 8... Read more
Department Of Justice Sets Sights On Apple In...
NEWS – The ball has finally dropped on the big Apple. The ball (metaphorically speaking) — an antitrust lawsuit filed in the U.S. on March 21 by the Department of Justice (DOJ) — came down following... Read more
New 13-inch M3 MacBook Air on sale for $999,...
Amazon has Apple’s new 13″ M3 MacBook Air on sale for $100 off MSRP for the first time, now just $999 shipped. Shipping is free: – 13″ MacBook Air (8GB RAM/256GB SSD/Space Gray): $999 $100 off MSRP... Read more
Amazon has Apple’s 9th-generation WiFi iPads...
Amazon has Apple’s 9th generation 10.2″ WiFi iPads on sale for $80-$100 off MSRP, starting only $249. Their prices are the lowest available for new iPads anywhere: – 10″ 64GB WiFi iPad (Space Gray or... Read more
Discounted 14-inch M3 MacBook Pros with 16GB...
Apple retailer Expercom has 14″ MacBook Pros with M3 CPUs and 16GB of standard memory discounted by up to $120 off Apple’s MSRP: – 14″ M3 MacBook Pro (16GB RAM/256GB SSD): $1691.06 $108 off MSRP – 14... Read more
Clearance 15-inch M2 MacBook Airs on sale for...
B&H Photo has Apple’s 15″ MacBook Airs with M2 CPUs (8GB RAM/256GB SSD) in stock today and on clearance sale for $999 in all four colors. Free 1-2 delivery is available to most US addresses.... Read more
Clearance 13-inch M1 MacBook Airs drop to onl...
B&H has Apple’s base 13″ M1 MacBook Air (Space Gray, Silver, & Gold) in stock and on clearance sale today for $300 off MSRP, only $699. Free 1-2 day shipping is available to most addresses in... Read more
New promo at Visible: Buy a new iPhone, get $...
Switch to Visible, and buy a new iPhone, and Visible will take $10 off their monthly Visible+ service for 24 months. Visible+ is normally $45 per month. With this promotion, the cost of Visible+ is... Read more
B&H has Apple’s 13-inch M2 MacBook Airs o...
B&H Photo has 13″ MacBook Airs with M2 CPUs and 256GB of storage in stock and on sale for $100 off Apple’s new MSRP, only $899. Free 1-2 day delivery is available to most US addresses. Their... Read more
Take advantage of Apple’s steep discounts on...
Apple has a full line of 16″ M3 Pro and M3 Max MacBook Pros available, Certified Refurbished, starting at $2119 and ranging up to $600 off MSRP. Each model features a new outer case, shipping is free... Read more

Jobs Board

Medical Assistant - Surgical Oncology- *Apple...
Medical Assistant - Surgical Oncology- Apple Hill Location: WellSpan Medical Group, York, PA Schedule: Full Time Sign-On Bonus Eligible Remote/Hybrid Regular Apply Read more
Omnichannel Associate - *Apple* Blossom Mal...
Omnichannel Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Cashier - *Apple* Blossom Mall - JCPenney (...
Cashier - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Blossom Mall Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Business Analyst | *Apple* Pay - Banco Popu...
Business Analyst | Apple PayApply now " Apply now + Apply Now + Start applying with LinkedIn Start + Please wait Date:Mar 19, 2024 Location: San Juan-Cupey, PR Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.