I am writing a GtkGrid-like container for my GUI library for Go, and I'm trying to write the actual layout part of the code.

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]

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...)

1 Answer 1


Are you guaranteed to get to any rectangle from any other? (are there any gaps?) I'm presuming so, otherwise you can't determine what the relative coordinates are for the map.

In that case, pick one arbitrarily and make that 0,0. Then it becomes a simple matter of walking the graph and assigning coordinates. If you require no negatives, then you'll need a second pass to shift everything +x/+y, but it should be O(n) at worst.

  • I was starting to think it was going to be something recursive like that; now I feel a little dumb for not realizing that earlier. Thanks!
    – andlabs
    Aug 31, 2014 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.