1 /*
2 * Copyright 2010, Haiku.
3 * Distributed under the terms of the MIT License.
4 *
5 * Authors:
6 * Clemens Zeidler <haiku@clemens-zeidler.de>
7 */
8
9 #include "Tiling.h"
10
11
12 #include "SATWindow.h"
13 #include "StackAndTile.h"
14 #include "Window.h"
15
16
17 using namespace std;
18
19
20 //#define DEBUG_TILING
21
22 #ifdef DEBUG_TILING
23 # define STRACE_TILING(x...) debug_printf("SAT Tiling: "x)
24 #else
25 # define STRACE_TILING(x...) ;
26 #endif
27
28
SATTiling(SATWindow * window)29 SATTiling::SATTiling(SATWindow* window)
30 :
31 fSATWindow(window),
32 fFreeAreaGroup(NULL)
33 {
34 _ResetSearchResults();
35 }
36
37
~SATTiling()38 SATTiling::~SATTiling()
39 {
40
41 }
42
43
44 bool
FindSnappingCandidates(SATGroup * group)45 SATTiling::FindSnappingCandidates(SATGroup* group)
46 {
47 _ResetSearchResults();
48
49 if (_IsTileableWindow(fSATWindow->GetWindow()) == false
50 || (group->CountItems() == 1
51 && _IsTileableWindow(group->WindowAt(0)->GetWindow()) == false))
52 return false;
53 if (fSATWindow->GetGroup() == group)
54 return false;
55
56 if (_FindFreeAreaInGroup(group)) {
57 fFreeAreaGroup = group;
58 _HighlightWindows(fFreeAreaGroup, true);
59 return true;
60 }
61
62 return false;
63 }
64
65
66 bool
JoinCandidates()67 SATTiling::JoinCandidates()
68 {
69 if (!fFreeAreaGroup)
70 return false;
71
72 if (!fFreeAreaGroup->AddWindow(fSATWindow, fFreeAreaLeft, fFreeAreaTop,
73 fFreeAreaRight, fFreeAreaBottom)) {
74 _ResetSearchResults();
75 return false;
76 }
77
78 fFreeAreaGroup->WindowAt(0)->DoGroupLayout();
79
80 _ResetSearchResults();
81 return true;
82 }
83
84
85 void
WindowLookChanged(window_look look)86 SATTiling::WindowLookChanged(window_look look)
87 {
88 SATGroup* group = fSATWindow->GetGroup();
89 if (group == NULL)
90 return;
91 if (_IsTileableWindow(fSATWindow->GetWindow()) == false)
92 group->RemoveWindow(fSATWindow);
93 }
94
95
96 bool
_IsTileableWindow(Window * window)97 SATTiling::_IsTileableWindow(Window* window)
98 {
99 if (window->Look() == B_DOCUMENT_WINDOW_LOOK)
100 return true;
101 if (window->Look() == B_TITLED_WINDOW_LOOK)
102 return true;
103 if (window->Look() == B_FLOATING_WINDOW_LOOK)
104 return true;
105 if (window->Look() == B_MODAL_WINDOW_LOOK)
106 return true;
107 if (window->Look() == B_BORDERED_WINDOW_LOOK)
108 return true;
109 return false;
110 }
111
112
113 bool
_FindFreeAreaInGroup(SATGroup * group)114 SATTiling::_FindFreeAreaInGroup(SATGroup* group)
115 {
116 if (_FindFreeAreaInGroup(group, Corner::kLeftTop))
117 return true;
118 if (_FindFreeAreaInGroup(group, Corner::kRightTop))
119 return true;
120 if (_FindFreeAreaInGroup(group, Corner::kLeftBottom))
121 return true;
122 if (_FindFreeAreaInGroup(group, Corner::kRightBottom))
123 return true;
124
125 return false;
126 }
127
128
129 bool
_FindFreeAreaInGroup(SATGroup * group,Corner::position_t cor)130 SATTiling::_FindFreeAreaInGroup(SATGroup* group, Corner::position_t cor)
131 {
132 BRect windowFrame = fSATWindow->CompleteWindowFrame();
133
134 const TabList* verticalTabs = group->VerticalTabs();
135 for (int i = 0; i < verticalTabs->CountItems(); i++) {
136 Tab* tab = verticalTabs->ItemAt(i);
137 const CrossingList* crossingList = tab->GetCrossingList();
138 for (int c = 0; c < crossingList->CountItems(); c++) {
139 Crossing* crossing = crossingList->ItemAt(c);
140 if (_InteresstingCrossing(crossing, cor, windowFrame)) {
141 if (_FindFreeArea(group, crossing, cor, windowFrame)) {
142 STRACE_TILING("SATTiling: free area found; corner %i\n",
143 cor);
144 return true;
145 }
146 }
147 }
148 }
149
150 return false;
151 }
152
153
154 const float kNoMatch = 999.f;
155 const float kMaxMatchingDistance = 12.f;
156
157
158 bool
_InteresstingCrossing(Crossing * crossing,Corner::position_t cor,BRect & windowFrame)159 SATTiling::_InteresstingCrossing(Crossing* crossing,
160 Corner::position_t cor, BRect& windowFrame)
161 {
162 const Corner* corner = crossing->GetOppositeCorner(cor);
163 if (corner->status != Corner::kFree)
164 return false;
165
166 float hTabPosition = crossing->HorizontalTab()->Position();
167 float vTabPosition = crossing->VerticalTab()->Position();
168 float hBorder = 0., vBorder = 0.;
169 float vDistance = -1., hDistance = -1.;
170 bool windowAtH = false, windowAtV = false;
171 switch (cor) {
172 case Corner::kLeftTop:
173 if (crossing->RightBottomCorner()->status == Corner::kUsed)
174 return false;
175 vBorder = windowFrame.left;
176 hBorder = windowFrame.top;
177 if (crossing->LeftBottomCorner()->status == Corner::kUsed)
178 windowAtV = true;
179 if (crossing->RightTopCorner()->status == Corner::kUsed)
180 windowAtH = true;
181 vDistance = vTabPosition - vBorder;
182 hDistance = hTabPosition - hBorder;
183 break;
184 case Corner::kRightTop:
185 if (crossing->LeftBottomCorner()->status == Corner::kUsed)
186 return false;
187 vBorder = windowFrame.right;
188 hBorder = windowFrame.top;
189 if (crossing->RightBottomCorner()->status == Corner::kUsed)
190 windowAtV = true;
191 if (crossing->LeftTopCorner()->status == Corner::kUsed)
192 windowAtH = true;
193 vDistance = vBorder - vTabPosition;
194 hDistance = hTabPosition - hBorder;
195 break;
196 case Corner::kLeftBottom:
197 if (crossing->RightTopCorner()->status == Corner::kUsed)
198 return false;
199 vBorder = windowFrame.left;
200 hBorder = windowFrame.bottom;
201 if (crossing->LeftTopCorner()->status == Corner::kUsed)
202 windowAtV = true;
203 if (crossing->RightBottomCorner()->status == Corner::kUsed)
204 windowAtH = true;
205 vDistance = vTabPosition - vBorder;
206 hDistance = hBorder - hTabPosition;
207 break;
208 case Corner::kRightBottom:
209 if (crossing->LeftTopCorner()->status == Corner::kUsed)
210 return false;
211 vBorder = windowFrame.right;
212 hBorder = windowFrame.bottom;
213 if (crossing->RightTopCorner()->status == Corner::kUsed)
214 windowAtV = true;
215 if (crossing->LeftBottomCorner()->status == Corner::kUsed)
216 windowAtH = true;
217 vDistance = vBorder - vTabPosition;
218 hDistance = hBorder - hTabPosition;
219 break;
220 };
221
222 bool hValid = false;
223 if (windowAtH && fabs(hDistance) < kMaxMatchingDistance
224 && vDistance < kMaxMatchingDistance)
225 hValid = true;
226 bool vValid = false;
227 if (windowAtV && fabs(vDistance) < kMaxMatchingDistance
228 && hDistance < kMaxMatchingDistance)
229 vValid = true;
230 if (!hValid && !vValid)
231 return false;
232
233 return true;
234 };
235
236
237 const float kBigAreaError = 1E+17;
238
239
240 bool
_FindFreeArea(SATGroup * group,const Crossing * crossing,Corner::position_t corner,BRect & windowFrame)241 SATTiling::_FindFreeArea(SATGroup* group, const Crossing* crossing,
242 Corner::position_t corner, BRect& windowFrame)
243 {
244 fFreeAreaLeft = fFreeAreaRight = fFreeAreaTop = fFreeAreaBottom = NULL;
245
246 const TabList* hTabs = group->HorizontalTabs();
247 const TabList* vTabs = group->VerticalTabs();
248 int32 hIndex = hTabs->IndexOf(crossing->HorizontalTab());
249 if (hIndex < 0)
250 return false;
251 int32 vIndex = vTabs->IndexOf(crossing->VerticalTab());
252 if (vIndex < 0)
253 return false;
254
255 Tab** endHTab = NULL, **endVTab = NULL;
256 int8 vSearchDirection = 1, hSearchDirection = 1;
257 switch (corner) {
258 case Corner::kLeftTop:
259 fFreeAreaLeft = crossing->VerticalTab();
260 fFreeAreaTop = crossing->HorizontalTab();
261 endHTab = &fFreeAreaBottom;
262 endVTab = &fFreeAreaRight;
263 vSearchDirection = 1;
264 hSearchDirection = 1;
265 break;
266 case Corner::kRightTop:
267 fFreeAreaRight = crossing->VerticalTab();
268 fFreeAreaTop = crossing->HorizontalTab();
269 endHTab = &fFreeAreaBottom;
270 endVTab = &fFreeAreaLeft;
271 vSearchDirection = -1;
272 hSearchDirection = 1;
273 break;
274 case Corner::kLeftBottom:
275 fFreeAreaLeft = crossing->VerticalTab();
276 fFreeAreaBottom = crossing->HorizontalTab();
277 endHTab = &fFreeAreaTop;
278 endVTab = &fFreeAreaRight;
279 vSearchDirection = 1;
280 hSearchDirection = -1;
281 break;
282 case Corner::kRightBottom:
283 fFreeAreaRight = crossing->VerticalTab();
284 fFreeAreaBottom = crossing->HorizontalTab();
285 endHTab = &fFreeAreaTop;
286 endVTab = &fFreeAreaLeft;
287 vSearchDirection = -1;
288 hSearchDirection = -1;
289 break;
290 };
291
292 Tab* bestLeftTab = NULL, *bestRightTab = NULL, *bestTopTab = NULL,
293 *bestBottomTab = NULL;
294 float bestError = kBigAreaError;
295 float error;
296 bool stop = false;
297 bool found = false;
298 int32 v = vIndex;
299 do {
300 v += vSearchDirection;
301 *endVTab = vTabs->ItemAt(v);
302 int32 h = hIndex;
303 do {
304 h += hSearchDirection;
305 *endHTab = hTabs->ItemAt(h);
306 if (!_CheckArea(group, corner, windowFrame, error)) {
307 if (h == hIndex + hSearchDirection)
308 stop = true;
309 break;
310 }
311 found = true;
312 if (error < bestError) {
313 bestError = error;
314 bestLeftTab = fFreeAreaLeft;
315 bestRightTab = fFreeAreaRight;
316 bestTopTab = fFreeAreaTop;
317 bestBottomTab = fFreeAreaBottom;
318 }
319 } while (*endHTab);
320 if (stop)
321 break;
322 } while (*endVTab);
323 if (!found)
324 return false;
325
326 fFreeAreaLeft = bestLeftTab;
327 fFreeAreaRight = bestRightTab;
328 fFreeAreaTop = bestTopTab;
329 fFreeAreaBottom = bestBottomTab;
330
331 return true;
332 }
333
334
335 bool
_HasOverlapp(SATGroup * group)336 SATTiling::_HasOverlapp(SATGroup* group)
337 {
338 BRect areaRect = _FreeAreaSize();
339 areaRect.InsetBy(1., 1.);
340
341 const TabList* hTabs = group->HorizontalTabs();
342 for (int32 h = 0; h < hTabs->CountItems(); h++) {
343 Tab* hTab = hTabs->ItemAt(h);
344 if (hTab->Position() >= areaRect.bottom)
345 return false;
346 const CrossingList* crossings = hTab->GetCrossingList();
347 for (int32 i = 0; i < crossings->CountItems(); i++) {
348 Crossing* leftTopCrossing = crossings->ItemAt(i);
349 Tab* vTab = leftTopCrossing->VerticalTab();
350 if (vTab->Position() > areaRect.right)
351 continue;
352 Corner* corner = leftTopCrossing->RightBottomCorner();
353 if (corner->status != Corner::kUsed)
354 continue;
355 BRect rect = corner->windowArea->Frame();
356 if (areaRect.Intersects(rect))
357 return true;
358 }
359 }
360 return false;
361 }
362
363
364 bool
_CheckArea(SATGroup * group,Corner::position_t corner,BRect & windowFrame,float & error)365 SATTiling::_CheckArea(SATGroup* group, Corner::position_t corner,
366 BRect& windowFrame, float& error)
367 {
368 error = kBigAreaError;
369 if (!_CheckMinFreeAreaSize())
370 return false;
371 // check if corner is in the free area
372 if (!_IsCornerInFreeArea(corner, windowFrame))
373 return false;
374
375 error = _FreeAreaError(windowFrame);
376 if (!_HasOverlapp(group))
377 return true;
378 return false;
379 }
380
381
382 bool
_CheckMinFreeAreaSize()383 SATTiling::_CheckMinFreeAreaSize()
384 {
385 // check if the area has a minimum size
386 if (fFreeAreaLeft && fFreeAreaRight
387 && fFreeAreaRight->Position() - fFreeAreaLeft->Position()
388 < 2 * kMaxMatchingDistance)
389 return false;
390 if (fFreeAreaBottom && fFreeAreaTop
391 && fFreeAreaBottom->Position() - fFreeAreaTop->Position()
392 < 2 * kMaxMatchingDistance)
393 return false;
394 return true;
395 }
396
397
398 float
_FreeAreaError(BRect & windowFrame)399 SATTiling::_FreeAreaError(BRect& windowFrame)
400 {
401 const float kEndTabError = 9999999;
402 float error = 0.;
403 if (fFreeAreaLeft && fFreeAreaRight)
404 error += pow(fFreeAreaRight->Position() - fFreeAreaLeft->Position()
405 - windowFrame.Width(), 2);
406 else
407 error += kEndTabError;
408 if (fFreeAreaBottom && fFreeAreaTop)
409 error += pow(fFreeAreaBottom->Position() - fFreeAreaTop->Position()
410 - windowFrame.Height(), 2);
411 else
412 error += kEndTabError;
413 return error;
414 }
415
416
417 bool
_IsCornerInFreeArea(Corner::position_t corner,BRect & frame)418 SATTiling::_IsCornerInFreeArea(Corner::position_t corner, BRect& frame)
419 {
420 BRect freeArea = _FreeAreaSize();
421
422 switch (corner) {
423 case Corner::kLeftTop:
424 if (freeArea.bottom - kMaxMatchingDistance > frame.top
425 && freeArea.right - kMaxMatchingDistance > frame.left)
426 return true;
427 break;
428 case Corner::kRightTop:
429 if (freeArea.bottom - kMaxMatchingDistance > frame.top
430 && freeArea.left + kMaxMatchingDistance < frame.right)
431 return true;
432 break;
433 case Corner::kLeftBottom:
434 if (freeArea.top + kMaxMatchingDistance < frame.bottom
435 && freeArea.right - kMaxMatchingDistance > frame.left)
436 return true;
437 break;
438 case Corner::kRightBottom:
439 if (freeArea.top + kMaxMatchingDistance < frame.bottom
440 && freeArea.left + kMaxMatchingDistance < frame.right)
441 return true;
442 break;
443 }
444
445 return false;
446 }
447
448
449 BRect
_FreeAreaSize()450 SATTiling::_FreeAreaSize()
451 {
452 // not to big to be be able to add/sub small float values
453 const float kBigValue = 9999999.;
454 float left = fFreeAreaLeft ? fFreeAreaLeft->Position() : -kBigValue;
455 float right = fFreeAreaRight ? fFreeAreaRight->Position() : kBigValue;
456 float top = fFreeAreaTop ? fFreeAreaTop->Position() : -kBigValue;
457 float bottom = fFreeAreaBottom ? fFreeAreaBottom->Position() : kBigValue;
458 return BRect(left, top, right, bottom);
459 }
460
461
462 void
_HighlightWindows(SATGroup * group,bool highlight)463 SATTiling::_HighlightWindows(SATGroup* group, bool highlight)
464 {
465 const TabList* hTabs = group->HorizontalTabs();
466 const TabList* vTabs = group->VerticalTabs();
467 // height light windows at all four sites
468 bool leftWindowsFound = _SearchHighlightWindow(fFreeAreaLeft, fFreeAreaTop, fFreeAreaBottom, hTabs,
469 fFreeAreaTop ? Corner::kLeftBottom : Corner::kLeftTop,
470 Decorator::REGION_RIGHT_BORDER, highlight);
471
472 bool topWindowsFound = _SearchHighlightWindow(fFreeAreaTop, fFreeAreaLeft, fFreeAreaRight, vTabs,
473 fFreeAreaLeft ? Corner::kRightTop : Corner::kLeftTop,
474 Decorator::REGION_BOTTOM_BORDER, highlight);
475
476 bool rightWindowsFound = _SearchHighlightWindow(fFreeAreaRight, fFreeAreaTop, fFreeAreaBottom, hTabs,
477 fFreeAreaTop ? Corner::kRightBottom : Corner::kRightTop,
478 Decorator::REGION_LEFT_BORDER, highlight);
479
480 bool bottomWindowsFound = _SearchHighlightWindow(fFreeAreaBottom, fFreeAreaLeft, fFreeAreaRight,
481 vTabs, fFreeAreaLeft ? Corner::kRightBottom : Corner::kLeftBottom,
482 Decorator::REGION_TOP_BORDER, highlight);
483
484 if (leftWindowsFound)
485 fSATWindow->HighlightBorders(Decorator::REGION_LEFT_BORDER, highlight);
486 if (topWindowsFound)
487 fSATWindow->HighlightBorders(Decorator::REGION_TOP_BORDER, highlight);
488 if (rightWindowsFound)
489 fSATWindow->HighlightBorders(Decorator::REGION_RIGHT_BORDER, highlight);
490 if (bottomWindowsFound) {
491 fSATWindow->HighlightBorders(Decorator::REGION_BOTTOM_BORDER,
492 highlight);
493 }
494 }
495
496
497 bool
_SearchHighlightWindow(Tab * tab,Tab * firstOrthTab,Tab * secondOrthTab,const TabList * orthTabs,Corner::position_t areaCorner,Decorator::Region region,bool highlight)498 SATTiling::_SearchHighlightWindow(Tab* tab, Tab* firstOrthTab,
499 Tab* secondOrthTab, const TabList* orthTabs, Corner::position_t areaCorner,
500 Decorator::Region region, bool highlight)
501 {
502 bool windowsFound = false;
503
504 if (!tab)
505 return false;
506
507 int8 searchDir = 1;
508 Tab* startOrthTab = NULL;
509 Tab* endOrthTab = NULL;
510 if (firstOrthTab) {
511 searchDir = 1;
512 startOrthTab = firstOrthTab;
513 endOrthTab = secondOrthTab;
514 }
515 else if (secondOrthTab) {
516 searchDir = -1;
517 startOrthTab = secondOrthTab;
518 endOrthTab = firstOrthTab;
519 }
520 else
521 return false;
522
523 int32 index = orthTabs->IndexOf(startOrthTab);
524 if (index < 0)
525 return false;
526
527 for (; index < orthTabs->CountItems() && index >= 0; index += searchDir) {
528 Tab* orthTab = orthTabs->ItemAt(index);
529 if (orthTab == endOrthTab)
530 break;
531 Crossing* crossing = tab->FindCrossing(orthTab);
532 if (!crossing)
533 continue;
534 Corner* corner = crossing->GetCorner(areaCorner);
535 if (corner->windowArea) {
536 _HighlightWindows(corner->windowArea, region, highlight);
537 windowsFound = true;
538 }
539 }
540 return windowsFound;
541 }
542
543
544 void
_HighlightWindows(WindowArea * area,Decorator::Region region,bool highlight)545 SATTiling::_HighlightWindows(WindowArea* area, Decorator::Region region,
546 bool highlight)
547 {
548 const SATWindowList& list = area->LayerOrder();
549 SATWindow* topWindow = list.ItemAt(list.CountItems() - 1);
550 if (topWindow == NULL)
551 return;
552 topWindow->HighlightBorders(region, highlight);
553 }
554
555
556 void
_ResetSearchResults()557 SATTiling::_ResetSearchResults()
558 {
559 if (!fFreeAreaGroup)
560 return;
561
562 _HighlightWindows(fFreeAreaGroup, false);
563 fFreeAreaGroup = NULL;
564 }
565