* Copyright 2010, Haiku.
* Distributed under the terms of the MIT License.
*
* Authors:
* Clemens Zeidler <haiku@clemens-zeidler.de>
*/
#include "Tiling.h"
#include "SATWindow.h"
#include "StackAndTile.h"
#include "Window.h"
using namespace std;
#ifdef DEBUG_TILING
# define STRACE_TILING(x...) debug_printf("SAT Tiling: "x)
#else
# define STRACE_TILING(x...) ;
#endif
SATTiling::SATTiling(SATWindow* window)
:
fSATWindow(window),
fFreeAreaGroup(NULL)
{
_ResetSearchResults();
}
SATTiling::~SATTiling()
{
}
bool
SATTiling::FindSnappingCandidates(SATGroup* group)
{
_ResetSearchResults();
if (_IsTileableWindow(fSATWindow->GetWindow()) == false
|| (group->CountItems() == 1
&& _IsTileableWindow(group->WindowAt(0)->GetWindow()) == false))
return false;
if (fSATWindow->GetGroup() == group)
return false;
if (_FindFreeAreaInGroup(group)) {
fFreeAreaGroup = group;
_HighlightWindows(fFreeAreaGroup, true);
return true;
}
return false;
}
bool
SATTiling::JoinCandidates()
{
if (!fFreeAreaGroup)
return false;
if (!fFreeAreaGroup->AddWindow(fSATWindow, fFreeAreaLeft, fFreeAreaTop,
fFreeAreaRight, fFreeAreaBottom)) {
_ResetSearchResults();
return false;
}
fFreeAreaGroup->WindowAt(0)->DoGroupLayout();
_ResetSearchResults();
return true;
}
void
SATTiling::WindowLookChanged(window_look look)
{
SATGroup* group = fSATWindow->GetGroup();
if (group == NULL)
return;
if (_IsTileableWindow(fSATWindow->GetWindow()) == false)
group->RemoveWindow(fSATWindow);
}
bool
SATTiling::_IsTileableWindow(Window* window)
{
if (window->Look() == B_DOCUMENT_WINDOW_LOOK)
return true;
if (window->Look() == B_TITLED_WINDOW_LOOK)
return true;
if (window->Look() == B_FLOATING_WINDOW_LOOK)
return true;
if (window->Look() == B_MODAL_WINDOW_LOOK)
return true;
if (window->Look() == B_BORDERED_WINDOW_LOOK)
return true;
return false;
}
bool
SATTiling::_FindFreeAreaInGroup(SATGroup* group)
{
if (_FindFreeAreaInGroup(group, Corner::kLeftTop))
return true;
if (_FindFreeAreaInGroup(group, Corner::kRightTop))
return true;
if (_FindFreeAreaInGroup(group, Corner::kLeftBottom))
return true;
if (_FindFreeAreaInGroup(group, Corner::kRightBottom))
return true;
return false;
}
bool
SATTiling::_FindFreeAreaInGroup(SATGroup* group, Corner::position_t cor)
{
BRect windowFrame = fSATWindow->CompleteWindowFrame();
const TabList* verticalTabs = group->VerticalTabs();
for (int i = 0; i < verticalTabs->CountItems(); i++) {
Tab* tab = verticalTabs->ItemAt(i);
const CrossingList* crossingList = tab->GetCrossingList();
for (int c = 0; c < crossingList->CountItems(); c++) {
Crossing* crossing = crossingList->ItemAt(c);
if (_InteresstingCrossing(crossing, cor, windowFrame)) {
if (_FindFreeArea(group, crossing, cor, windowFrame)) {
STRACE_TILING("SATTiling: free area found; corner %i\n",
cor);
return true;
}
}
}
}
return false;
}
const float kNoMatch = 999.f;
const float kMaxMatchingDistance = 12.f;
bool
SATTiling::_InteresstingCrossing(Crossing* crossing,
Corner::position_t cor, BRect& windowFrame)
{
const Corner* corner = crossing->GetOppositeCorner(cor);
if (corner->status != Corner::kFree)
return false;
float hTabPosition = crossing->HorizontalTab()->Position();
float vTabPosition = crossing->VerticalTab()->Position();
float hBorder = 0., vBorder = 0.;
float vDistance = -1., hDistance = -1.;
bool windowAtH = false, windowAtV = false;
switch (cor) {
case Corner::kLeftTop:
if (crossing->RightBottomCorner()->status == Corner::kUsed)
return false;
vBorder = windowFrame.left;
hBorder = windowFrame.top;
if (crossing->LeftBottomCorner()->status == Corner::kUsed)
windowAtV = true;
if (crossing->RightTopCorner()->status == Corner::kUsed)
windowAtH = true;
vDistance = vTabPosition - vBorder;
hDistance = hTabPosition - hBorder;
break;
case Corner::kRightTop:
if (crossing->LeftBottomCorner()->status == Corner::kUsed)
return false;
vBorder = windowFrame.right;
hBorder = windowFrame.top;
if (crossing->RightBottomCorner()->status == Corner::kUsed)
windowAtV = true;
if (crossing->LeftTopCorner()->status == Corner::kUsed)
windowAtH = true;
vDistance = vBorder - vTabPosition;
hDistance = hTabPosition - hBorder;
break;
case Corner::kLeftBottom:
if (crossing->RightTopCorner()->status == Corner::kUsed)
return false;
vBorder = windowFrame.left;
hBorder = windowFrame.bottom;
if (crossing->LeftTopCorner()->status == Corner::kUsed)
windowAtV = true;
if (crossing->RightBottomCorner()->status == Corner::kUsed)
windowAtH = true;
vDistance = vTabPosition - vBorder;
hDistance = hBorder - hTabPosition;
break;
case Corner::kRightBottom:
if (crossing->LeftTopCorner()->status == Corner::kUsed)
return false;
vBorder = windowFrame.right;
hBorder = windowFrame.bottom;
if (crossing->RightTopCorner()->status == Corner::kUsed)
windowAtV = true;
if (crossing->LeftBottomCorner()->status == Corner::kUsed)
windowAtH = true;
vDistance = vBorder - vTabPosition;
hDistance = hBorder - hTabPosition;
break;
};
bool hValid = false;
if (windowAtH && fabs(hDistance) < kMaxMatchingDistance
&& vDistance < kMaxMatchingDistance)
hValid = true;
bool vValid = false;
if (windowAtV && fabs(vDistance) < kMaxMatchingDistance
&& hDistance < kMaxMatchingDistance)
vValid = true;
if (!hValid && !vValid)
return false;
return true;
};
const float kBigAreaError = 1E+17;
bool
SATTiling::_FindFreeArea(SATGroup* group, const Crossing* crossing,
Corner::position_t corner, BRect& windowFrame)
{
fFreeAreaLeft = fFreeAreaRight = fFreeAreaTop = fFreeAreaBottom = NULL;
const TabList* hTabs = group->HorizontalTabs();
const TabList* vTabs = group->VerticalTabs();
int32 hIndex = hTabs->IndexOf(crossing->HorizontalTab());
if (hIndex < 0)
return false;
int32 vIndex = vTabs->IndexOf(crossing->VerticalTab());
if (vIndex < 0)
return false;
Tab** endHTab = NULL, **endVTab = NULL;
int8 vSearchDirection = 1, hSearchDirection = 1;
switch (corner) {
case Corner::kLeftTop:
fFreeAreaLeft = crossing->VerticalTab();
fFreeAreaTop = crossing->HorizontalTab();
endHTab = &fFreeAreaBottom;
endVTab = &fFreeAreaRight;
vSearchDirection = 1;
hSearchDirection = 1;
break;
case Corner::kRightTop:
fFreeAreaRight = crossing->VerticalTab();
fFreeAreaTop = crossing->HorizontalTab();
endHTab = &fFreeAreaBottom;
endVTab = &fFreeAreaLeft;
vSearchDirection = -1;
hSearchDirection = 1;
break;
case Corner::kLeftBottom:
fFreeAreaLeft = crossing->VerticalTab();
fFreeAreaBottom = crossing->HorizontalTab();
endHTab = &fFreeAreaTop;
endVTab = &fFreeAreaRight;
vSearchDirection = 1;
hSearchDirection = -1;
break;
case Corner::kRightBottom:
fFreeAreaRight = crossing->VerticalTab();
fFreeAreaBottom = crossing->HorizontalTab();
endHTab = &fFreeAreaTop;
endVTab = &fFreeAreaLeft;
vSearchDirection = -1;
hSearchDirection = -1;
break;
};
Tab* bestLeftTab = NULL, *bestRightTab = NULL, *bestTopTab = NULL,
*bestBottomTab = NULL;
float bestError = kBigAreaError;
float error;
bool stop = false;
bool found = false;
int32 v = vIndex;
do {
v += vSearchDirection;
*endVTab = vTabs->ItemAt(v);
int32 h = hIndex;
do {
h += hSearchDirection;
*endHTab = hTabs->ItemAt(h);
if (!_CheckArea(group, corner, windowFrame, error)) {
if (h == hIndex + hSearchDirection)
stop = true;
break;
}
found = true;
if (error < bestError) {
bestError = error;
bestLeftTab = fFreeAreaLeft;
bestRightTab = fFreeAreaRight;
bestTopTab = fFreeAreaTop;
bestBottomTab = fFreeAreaBottom;
}
} while (*endHTab);
if (stop)
break;
} while (*endVTab);
if (!found)
return false;
fFreeAreaLeft = bestLeftTab;
fFreeAreaRight = bestRightTab;
fFreeAreaTop = bestTopTab;
fFreeAreaBottom = bestBottomTab;
return true;
}
bool
SATTiling::_HasOverlapp(SATGroup* group)
{
BRect areaRect = _FreeAreaSize();
areaRect.InsetBy(1., 1.);
const TabList* hTabs = group->HorizontalTabs();
for (int32 h = 0; h < hTabs->CountItems(); h++) {
Tab* hTab = hTabs->ItemAt(h);
if (hTab->Position() >= areaRect.bottom)
return false;
const CrossingList* crossings = hTab->GetCrossingList();
for (int32 i = 0; i < crossings->CountItems(); i++) {
Crossing* leftTopCrossing = crossings->ItemAt(i);
Tab* vTab = leftTopCrossing->VerticalTab();
if (vTab->Position() > areaRect.right)
continue;
Corner* corner = leftTopCrossing->RightBottomCorner();
if (corner->status != Corner::kUsed)
continue;
BRect rect = corner->windowArea->Frame();
if (areaRect.Intersects(rect))
return true;
}
}
return false;
}
bool
SATTiling::_CheckArea(SATGroup* group, Corner::position_t corner,
BRect& windowFrame, float& error)
{
error = kBigAreaError;
if (!_CheckMinFreeAreaSize())
return false;
if (!_IsCornerInFreeArea(corner, windowFrame))
return false;
error = _FreeAreaError(windowFrame);
if (!_HasOverlapp(group))
return true;
return false;
}
bool
SATTiling::_CheckMinFreeAreaSize()
{
if (fFreeAreaLeft && fFreeAreaRight
&& fFreeAreaRight->Position() - fFreeAreaLeft->Position()
< 2 * kMaxMatchingDistance)
return false;
if (fFreeAreaBottom && fFreeAreaTop
&& fFreeAreaBottom->Position() - fFreeAreaTop->Position()
< 2 * kMaxMatchingDistance)
return false;
return true;
}
float
SATTiling::_FreeAreaError(BRect& windowFrame)
{
const float kEndTabError = 9999999;
float error = 0.;
if (fFreeAreaLeft && fFreeAreaRight)
error += pow(fFreeAreaRight->Position() - fFreeAreaLeft->Position()
- windowFrame.Width(), 2);
else
error += kEndTabError;
if (fFreeAreaBottom && fFreeAreaTop)
error += pow(fFreeAreaBottom->Position() - fFreeAreaTop->Position()
- windowFrame.Height(), 2);
else
error += kEndTabError;
return error;
}
bool
SATTiling::_IsCornerInFreeArea(Corner::position_t corner, BRect& frame)
{
BRect freeArea = _FreeAreaSize();
switch (corner) {
case Corner::kLeftTop:
if (freeArea.bottom - kMaxMatchingDistance > frame.top
&& freeArea.right - kMaxMatchingDistance > frame.left)
return true;
break;
case Corner::kRightTop:
if (freeArea.bottom - kMaxMatchingDistance > frame.top
&& freeArea.left + kMaxMatchingDistance < frame.right)
return true;
break;
case Corner::kLeftBottom:
if (freeArea.top + kMaxMatchingDistance < frame.bottom
&& freeArea.right - kMaxMatchingDistance > frame.left)
return true;
break;
case Corner::kRightBottom:
if (freeArea.top + kMaxMatchingDistance < frame.bottom
&& freeArea.left + kMaxMatchingDistance < frame.right)
return true;
break;
}
return false;
}
BRect
SATTiling::_FreeAreaSize()
{
const float kBigValue = 9999999.;
float left = fFreeAreaLeft ? fFreeAreaLeft->Position() : -kBigValue;
float right = fFreeAreaRight ? fFreeAreaRight->Position() : kBigValue;
float top = fFreeAreaTop ? fFreeAreaTop->Position() : -kBigValue;
float bottom = fFreeAreaBottom ? fFreeAreaBottom->Position() : kBigValue;
return BRect(left, top, right, bottom);
}
void
SATTiling::_HighlightWindows(SATGroup* group, bool highlight)
{
const TabList* hTabs = group->HorizontalTabs();
const TabList* vTabs = group->VerticalTabs();
bool leftWindowsFound = _SearchHighlightWindow(fFreeAreaLeft, fFreeAreaTop, fFreeAreaBottom, hTabs,
fFreeAreaTop ? Corner::kLeftBottom : Corner::kLeftTop,
Decorator::REGION_RIGHT_BORDER, highlight);
bool topWindowsFound = _SearchHighlightWindow(fFreeAreaTop, fFreeAreaLeft, fFreeAreaRight, vTabs,
fFreeAreaLeft ? Corner::kRightTop : Corner::kLeftTop,
Decorator::REGION_BOTTOM_BORDER, highlight);
bool rightWindowsFound = _SearchHighlightWindow(fFreeAreaRight, fFreeAreaTop, fFreeAreaBottom, hTabs,
fFreeAreaTop ? Corner::kRightBottom : Corner::kRightTop,
Decorator::REGION_LEFT_BORDER, highlight);
bool bottomWindowsFound = _SearchHighlightWindow(fFreeAreaBottom, fFreeAreaLeft, fFreeAreaRight,
vTabs, fFreeAreaLeft ? Corner::kRightBottom : Corner::kLeftBottom,
Decorator::REGION_TOP_BORDER, highlight);
if (leftWindowsFound)
fSATWindow->HighlightBorders(Decorator::REGION_LEFT_BORDER, highlight);
if (topWindowsFound)
fSATWindow->HighlightBorders(Decorator::REGION_TOP_BORDER, highlight);
if (rightWindowsFound)
fSATWindow->HighlightBorders(Decorator::REGION_RIGHT_BORDER, highlight);
if (bottomWindowsFound) {
fSATWindow->HighlightBorders(Decorator::REGION_BOTTOM_BORDER,
highlight);
}
}
bool
SATTiling::_SearchHighlightWindow(Tab* tab, Tab* firstOrthTab,
Tab* secondOrthTab, const TabList* orthTabs, Corner::position_t areaCorner,
Decorator::Region region, bool highlight)
{
bool windowsFound = false;
if (!tab)
return false;
int8 searchDir = 1;
Tab* startOrthTab = NULL;
Tab* endOrthTab = NULL;
if (firstOrthTab) {
searchDir = 1;
startOrthTab = firstOrthTab;
endOrthTab = secondOrthTab;
}
else if (secondOrthTab) {
searchDir = -1;
startOrthTab = secondOrthTab;
endOrthTab = firstOrthTab;
}
else
return false;
int32 index = orthTabs->IndexOf(startOrthTab);
if (index < 0)
return false;
for (; index < orthTabs->CountItems() && index >= 0; index += searchDir) {
Tab* orthTab = orthTabs->ItemAt(index);
if (orthTab == endOrthTab)
break;
Crossing* crossing = tab->FindCrossing(orthTab);
if (!crossing)
continue;
Corner* corner = crossing->GetCorner(areaCorner);
if (corner->windowArea) {
_HighlightWindows(corner->windowArea, region, highlight);
windowsFound = true;
}
}
return windowsFound;
}
void
SATTiling::_HighlightWindows(WindowArea* area, Decorator::Region region,
bool highlight)
{
const SATWindowList& list = area->LayerOrder();
SATWindow* topWindow = list.ItemAt(list.CountItems() - 1);
if (topWindow == NULL)
return;
topWindow->HighlightBorders(region, highlight);
}
void
SATTiling::_ResetSearchResults()
{
if (!fFreeAreaGroup)
return;
_HighlightWindows(fFreeAreaGroup, false);
fFreeAreaGroup = NULL;
}
