Basically, I have an unordered list of controls. Each control is a rectangle, and each list entry contains a pointer to the control to its north, south, east, and west. What I don't know is how to convert this back into a grid efficiently.
At first I thought I could use "the top-left control" to mark (0, 0) on the grid. But what's the top-left of
[ ][ ][X] [ ][X][X] [X][X][X]
Any other solution I can think of runs in at least O(n^k) time, since I need to traverse the list multiple times to figure out what each row is, etc.
So what other approach can I use? Thanks.
The algorithm will need to be able to start from any control in the list. (Go programmers: the reason for this is that the list is a map.)
I can say that there will be no freestanding controls (all controls must be attached to another control, but can be attached on any side at any time). (Except, of course, if there is only one control at all, but I imagine this scenario falling out of the solution.)
(I hope this is in the right subdomain...)