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][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...)
I have an unordered list of rectangles and their neighbors on four sides with no origin. How can I efficiently convert this into a grid?
algorithms;data structures;go
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.