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
