WM: grouping applications (TAI)

[Matthew Woehlke]

Maciej Pilichowski wrote:
> On Saturday 02 May 2009 00:28:57 Matthew Woehlke wrote:
> 
>>> In GAI if I would like to go spatial navigating I would really
>>> like to go up or down, not only next/previous.
>> previous/next would "wrap" much like tab order of widgets, so you
>> would (eventually) get everywhere. 
> 
> So I understood you correctly before -- it is a sequence switch :-D
> 
> I started writing that I am not convinced, but then you convinced me, 
> so I delete everything in "unconvinced" state :-D
> 
> 
>> Not considering wrapping, it is still possible that previous/left
>> and next/right are not equivalent. 
> 
> Sure.
> 
>> +---+---+
>> | A |   |
>> |   | C |
>> +---+   |
>> | B +---+
>> |   | D |
>> +---+---+
>>
>> ...from B, left might go to C (especially if the part of C along B
>> is taller than D), but next would always go to D
>> (because C follows 
>> A, next can never go to C except from A).
> 
> I sense here, that you calculated B->D from exclusion.

Something like that. As in the 'Switchers as arrangement managers' 
thread, you've got an ordered list of all siblings.

> This is 
> interesting mathematical challenge, but even without much thought I 
> think it is not doable because there are cases when you get clash. 
> I.e. you end up with mutually depend exclusions.
> 
> Unless you say, that we try first exclusions, and for all clashes we 
> compute sequence from geometry + take-first decision.

I don't think the problem is unsolvable, just that the solution might 
not be optimal.

GAI is basically a grid, where a window can span more than one cell. The 
easiest solution is to simply to walk the grid; when you encounter a 
window not already in the list, add it to the list.

A better algorithm would be to break the grid down into a BSP tree with 
each branch containing only whole windows (i.e. do the splits in a way 
such that no window may belong to multiple branches). Any (sub)grids 
that cannot be broken down in this way are treated as leaves, and 
ordered with grid-walk. Otherwise order is done by tree-walk.

This would result in the more natural order (A,B,C,D) for things like this:

+-+-+
|A| |
+-+ |
|B|D|
+-+ |
|C| |
+-+-+

(Of course, the GAI implementation may /force/ a BSP, in which case 
there is not really an issue. I'd prefer, however, if it didn't. I've 
seen a good implementation of "window" tiles that is grid-based, so I 
can describe how it should work, if needed.)

>> (I'm assuming that previous/next are bias-horizontal... which maybe
>> should be an option :-).
> 
> Nah, this one can be fixed :-) Btw. spatial alg. must also have bias.

Well it at least needs to cope with RTL :-).

How does u/d/l/r need a bias? (Or do you mean bias as in how I am 
assuming that, when "left" has two choices of window, always take the 
one with the longer shared border?)

-- 
Matthew
Please do not quote my e-mail address unobfuscated in message bodies.
-- 
"Any customer can have a car painted any color that he wants...
...so long as it is black." -- Henry Ford