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 29 SATTiling::SATTiling(SATWindow* window) 30 : 31 fSATWindow(window), 32 fFreeAreaGroup(NULL) 33 { 34 _ResetSearchResults(); 35 } 36 37 38 SATTiling::~SATTiling() 39 { 40 41 } 42 43 44 bool 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 557 SATTiling::_ResetSearchResults() 558 { 559 if (!fFreeAreaGroup) 560 return; 561 562 _HighlightWindows(fFreeAreaGroup, false); 563 fFreeAreaGroup = NULL; 564 } 565