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
17using 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
29SATTiling::SATTiling(SATWindow* window)
30	:
31	fSATWindow(window),
32	fFreeAreaGroup(NULL)
33{
34	_ResetSearchResults();
35}
36
37
38SATTiling::~SATTiling()
39{
40
41}
42
43
44bool
45SATTiling::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
66bool
67SATTiling::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
85void
86SATTiling::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
96bool
97SATTiling::_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
113bool
114SATTiling::_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
129bool
130SATTiling::_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
154const float kNoMatch = 999.f;
155const float kMaxMatchingDistance = 12.f;
156
157
158bool
159SATTiling::_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
237const float kBigAreaError = 1E+17;
238
239
240bool
241SATTiling::_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
335bool
336SATTiling::_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
364bool
365SATTiling::_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
382bool
383SATTiling::_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
398float
399SATTiling::_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
417bool
418SATTiling::_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
449BRect
450SATTiling::_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
462void
463SATTiling::_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
497bool
498SATTiling::_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
544void
545SATTiling::_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
556void
557SATTiling::_ResetSearchResults()
558{
559	if (!fFreeAreaGroup)
560		return;
561
562	_HighlightWindows(fFreeAreaGroup, false);
563	fFreeAreaGroup = NULL;
564}
565