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
10#include "SATGroup.h"
11
12#include <vector>
13
14#include <Debug.h>
15#include <Message.h>
16
17#include "Desktop.h"
18
19#include "SATWindow.h"
20#include "StackAndTile.h"
21#include "Window.h"
22
23
24using namespace std;
25using namespace LinearProgramming;
26
27
28const float kExtentPenalty = 1;
29const float kHighPenalty = 100;
30const float kInequalityPenalty = 10000;
31
32
33WindowArea::WindowArea(Crossing* leftTop, Crossing* rightTop,
34	Crossing* leftBottom, Crossing* rightBottom)
35	:
36	fGroup(NULL),
37
38	fLeftTopCrossing(leftTop),
39	fRightTopCrossing(rightTop),
40	fLeftBottomCrossing(leftBottom),
41	fRightBottomCrossing(rightBottom),
42
43	fMinWidthConstraint(NULL),
44	fMinHeightConstraint(NULL),
45	fMaxWidthConstraint(NULL),
46	fMaxHeightConstraint(NULL),
47	fWidthConstraint(NULL),
48	fHeightConstraint(NULL)
49{
50}
51
52
53WindowArea::~WindowArea()
54{
55	if (fGroup)
56		fGroup->WindowAreaRemoved(this);
57
58	_CleanupCorners();
59	fGroup->fWindowAreaList.RemoveItem(this);
60
61	_UninitConstraints();
62}
63
64
65bool
66WindowArea::Init(SATGroup* group)
67{
68	_UninitConstraints();
69
70	if (group != NULL && group->fWindowAreaList.AddItem(this) == false)
71		return false;
72
73	fGroup = group;
74
75	LinearSpec* linearSpec = fGroup->GetLinearSpec();
76
77	fMinWidthConstraint = linearSpec->AddConstraint(1.0, RightVar(), -1.0,
78		LeftVar(), kGE, 0);
79	fMinHeightConstraint = linearSpec->AddConstraint(1.0, BottomVar(), -1.0,
80		TopVar(), kGE, 0);
81
82	fMaxWidthConstraint = linearSpec->AddConstraint(1.0, RightVar(), -1.0,
83		LeftVar(), kLE, 0, kInequalityPenalty, kInequalityPenalty);
84	fMaxHeightConstraint = linearSpec->AddConstraint(1.0, BottomVar(), -1.0,
85		TopVar(), kLE, 0, kInequalityPenalty, kInequalityPenalty);
86
87	// Width and height have soft constraints
88	fWidthConstraint = linearSpec->AddConstraint(1.0, RightVar(), -1.0,
89		LeftVar(), kEQ, 0, kExtentPenalty,
90		kExtentPenalty);
91	fHeightConstraint = linearSpec->AddConstraint(-1.0, TopVar(), 1.0,
92		BottomVar(), kEQ, 0, kExtentPenalty,
93		kExtentPenalty);
94
95	if (!fMinWidthConstraint || !fMinHeightConstraint || !fWidthConstraint
96		|| !fHeightConstraint || !fMaxWidthConstraint
97		|| !fMaxHeightConstraint)
98		return false;
99
100	return true;
101}
102
103
104void
105WindowArea::DoGroupLayout()
106{
107	SATWindow* parentWindow = fWindowLayerOrder.ItemAt(0);
108	if (parentWindow == NULL)
109		return;
110
111	BRect frame = parentWindow->CompleteWindowFrame();
112	// Make it also work for solver which don't support negative variables
113	frame.OffsetBy(kMakePositiveOffset, kMakePositiveOffset);
114
115	// adjust window size soft constraints
116	fWidthConstraint->SetRightSide(frame.Width());
117	fHeightConstraint->SetRightSide(frame.Height());
118
119	LinearSpec* linearSpec = fGroup->GetLinearSpec();
120	Constraint* leftConstraint = linearSpec->AddConstraint(1.0, LeftVar(),
121		kEQ, frame.left);
122	Constraint* topConstraint = linearSpec->AddConstraint(1.0, TopVar(), kEQ,
123		frame.top);
124
125	// give soft constraints a high penalty
126	fWidthConstraint->SetPenaltyNeg(kHighPenalty);
127	fWidthConstraint->SetPenaltyPos(kHighPenalty);
128	fHeightConstraint->SetPenaltyNeg(kHighPenalty);
129	fHeightConstraint->SetPenaltyPos(kHighPenalty);
130
131	// After we set the new parameter solve and apply the new layout.
132	ResultType result;
133	for (int32 tries = 0; tries < 15; tries++) {
134		result = fGroup->GetLinearSpec()->Solve();
135		if (result == kInfeasible) {
136			debug_printf("can't solve constraints!\n");
137			break;
138		}
139		if (result == kOptimal) {
140			const WindowAreaList& areas = fGroup->GetAreaList();
141			for (int32 i = 0; i < areas.CountItems(); i++) {
142				WindowArea* area = areas.ItemAt(i);
143				area->_MoveToSAT(parentWindow);
144			}
145			break;
146		}
147	}
148
149	// set penalties back to normal
150	fWidthConstraint->SetPenaltyNeg(kExtentPenalty);
151	fWidthConstraint->SetPenaltyPos(kExtentPenalty);
152	fHeightConstraint->SetPenaltyNeg(kExtentPenalty);
153	fHeightConstraint->SetPenaltyPos(kExtentPenalty);
154
155	linearSpec->RemoveConstraint(leftConstraint);
156	linearSpec->RemoveConstraint(topConstraint);
157}
158
159
160void
161WindowArea::UpdateSizeLimits()
162{
163	_UpdateConstraintValues();
164}
165
166
167void
168WindowArea::UpdateSizeConstaints(const BRect& frame)
169{
170	// adjust window size soft constraints
171	fWidthConstraint->SetRightSide(frame.Width());
172	fHeightConstraint->SetRightSide(frame.Height());
173}
174
175
176bool
177WindowArea::MoveWindowToPosition(SATWindow* window, int32 index)
178{
179	int32 oldIndex = fWindowList.IndexOf(window);
180	ASSERT(oldIndex != index);
181	return fWindowList.MoveItem(oldIndex, index);
182}
183
184
185SATWindow*
186WindowArea::TopWindow()
187{
188	return fWindowLayerOrder.ItemAt(fWindowLayerOrder.CountItems() - 1);
189}
190
191
192void
193WindowArea::_UpdateConstraintValues()
194{
195	SATWindow* topWindow = TopWindow();
196	if (topWindow == NULL)
197		return;
198
199	int32 minWidth, maxWidth;
200	int32 minHeight, maxHeight;
201	SATWindow* window = fWindowList.ItemAt(0);
202	window->GetSizeLimits(&minWidth, &maxWidth, &minHeight, &maxHeight);
203	for (int32 i = 1; i < fWindowList.CountItems(); i++) {
204		window = fWindowList.ItemAt(i);
205		// size limit constraints
206		int32 minW, maxW;
207		int32 minH, maxH;
208		window->GetSizeLimits(&minW, &maxW, &minH, &maxH);
209		if (minWidth < minW)
210			minWidth = minW;
211		if (minHeight < minH)
212			minHeight = minH;
213		if (maxWidth < maxW)
214			maxWidth = maxW;
215		if (maxHeight < maxH)
216			maxHeight = maxH;
217	}
218	// the current solver don't like big values
219	const int32 kMaxSolverValue = 5000;
220	if (minWidth > kMaxSolverValue)
221		minWidth = kMaxSolverValue;
222	if (minHeight > kMaxSolverValue)
223		minHeight = kMaxSolverValue;
224	if (maxWidth > kMaxSolverValue)
225		maxWidth = kMaxSolverValue;
226	if (maxHeight > kMaxSolverValue)
227		maxHeight = kMaxSolverValue;
228
229	topWindow->AddDecorator(&minWidth, &maxWidth, &minHeight, &maxHeight);
230	fMinWidthConstraint->SetRightSide(minWidth);
231	fMinHeightConstraint->SetRightSide(minHeight);
232
233	fMaxWidthConstraint->SetRightSide(maxWidth);
234	fMaxHeightConstraint->SetRightSide(maxHeight);
235
236	BRect frame = topWindow->CompleteWindowFrame();
237	fWidthConstraint->SetRightSide(frame.Width());
238	fHeightConstraint->SetRightSide(frame.Height());
239}
240
241
242bool
243WindowArea::_AddWindow(SATWindow* window, SATWindow* after)
244{
245	if (after) {
246		int32 indexAfter = fWindowList.IndexOf(after);
247		if (!fWindowList.AddItem(window, indexAfter + 1))
248			return false;
249	} else if (fWindowList.AddItem(window) == false)
250		return false;
251
252	AcquireReference();
253
254	if (fWindowList.CountItems() <= 1)
255		_InitCorners();
256
257	fWindowLayerOrder.AddItem(window);
258
259	_UpdateConstraintValues();
260	return true;
261}
262
263
264bool
265WindowArea::_RemoveWindow(SATWindow* window)
266{
267	if (!fWindowList.RemoveItem(window))
268		return false;
269
270	fWindowLayerOrder.RemoveItem(window);
271	_UpdateConstraintValues();
272
273	window->RemovedFromArea(this);
274	ReleaseReference();
275	return true;
276}
277
278
279Tab*
280WindowArea::LeftTab()
281{
282	return fLeftTopCrossing->VerticalTab();
283}
284
285
286Tab*
287WindowArea::RightTab()
288{
289	return fRightBottomCrossing->VerticalTab();
290}
291
292
293Tab*
294WindowArea::TopTab()
295{
296	return fLeftTopCrossing->HorizontalTab();
297}
298
299
300Tab*
301WindowArea::BottomTab()
302{
303	return fRightBottomCrossing->HorizontalTab();
304}
305
306
307BRect
308WindowArea::Frame()
309{
310	return BRect(fLeftTopCrossing->VerticalTab()->Position(),
311		fLeftTopCrossing->HorizontalTab()->Position(),
312		fRightBottomCrossing->VerticalTab()->Position(),
313		fRightBottomCrossing->HorizontalTab()->Position());
314}
315
316
317bool
318WindowArea::PropagateToGroup(SATGroup* group)
319{
320	BReference<Crossing> newLeftTop = _CrossingByPosition(fLeftTopCrossing,
321		group);
322	BReference<Crossing> newRightTop = _CrossingByPosition(fRightTopCrossing,
323		group);
324	BReference<Crossing> newLeftBottom = _CrossingByPosition(
325		fLeftBottomCrossing, group);
326	BReference<Crossing> newRightBottom = _CrossingByPosition(
327		fRightBottomCrossing, group);
328
329	if (!newLeftTop || !newRightTop || !newLeftBottom || !newRightBottom)
330		return false;
331
332	// hold a ref to the crossings till we cleaned up everything
333	BReference<Crossing> oldLeftTop = fLeftTopCrossing;
334	BReference<Crossing> oldRightTop = fRightTopCrossing;
335	BReference<Crossing> oldLeftBottom = fLeftBottomCrossing;
336	BReference<Crossing> oldRightBottom = fRightBottomCrossing;
337
338	fLeftTopCrossing = newLeftTop;
339	fRightTopCrossing = newRightTop;
340	fLeftBottomCrossing = newLeftBottom;
341	fRightBottomCrossing = newRightBottom;
342
343	_InitCorners();
344
345	BReference<SATGroup> oldGroup = fGroup;
346	// manage constraints
347	if (Init(group) == false)
348		return false;
349
350	oldGroup->fWindowAreaList.RemoveItem(this);
351	for (int32 i = 0; i < fWindowList.CountItems(); i++) {
352		SATWindow* window = fWindowList.ItemAt(i);
353		if (oldGroup->fSATWindowList.RemoveItem(window) == false)
354			return false;
355		if (group->fSATWindowList.AddItem(window) == false) {
356			_UninitConstraints();
357			return false;
358		}
359	}
360
361	_UpdateConstraintValues();
362
363	return true;
364}
365
366
367bool
368WindowArea::MoveToTopLayer(SATWindow* window)
369{
370	if (!fWindowLayerOrder.RemoveItem(window))
371		return false;
372	return fWindowLayerOrder.AddItem(window);
373}
374
375
376void
377WindowArea::_UninitConstraints()
378{
379	LinearSpec* linearSpec = fGroup->GetLinearSpec();
380
381	linearSpec->RemoveConstraint(fMinWidthConstraint, true);
382	linearSpec->RemoveConstraint(fMinHeightConstraint, true);
383	linearSpec->RemoveConstraint(fMaxWidthConstraint, true);
384	linearSpec->RemoveConstraint(fMaxHeightConstraint, true);
385	linearSpec->RemoveConstraint(fWidthConstraint, true);
386	linearSpec->RemoveConstraint(fHeightConstraint, true);
387
388	fMinWidthConstraint = NULL;
389	fMinHeightConstraint = NULL;
390	fMaxWidthConstraint = NULL;
391	fMaxHeightConstraint = NULL;
392	fWidthConstraint = NULL;
393	fHeightConstraint = NULL;
394}
395
396
397BReference<Crossing>
398WindowArea::_CrossingByPosition(Crossing* crossing, SATGroup* group)
399{
400	BReference<Crossing> crossRef = NULL;
401
402	Tab* oldHTab = crossing->HorizontalTab();
403	BReference<Tab> hTab = group->FindHorizontalTab(oldHTab->Position());
404	if (!hTab)
405		hTab = group->_AddHorizontalTab(oldHTab->Position());
406	if (!hTab)
407		return crossRef;
408
409	Tab* oldVTab = crossing->VerticalTab();
410	crossRef = hTab->FindCrossing(oldVTab->Position());
411	if (crossRef)
412		return crossRef;
413
414	BReference<Tab> vTab = group->FindVerticalTab(oldVTab->Position());
415	if (!vTab)
416		vTab = group->_AddVerticalTab(oldVTab->Position());
417	if (!vTab)
418		return crossRef;
419
420	return hTab->AddCrossing(vTab);
421}
422
423
424void
425WindowArea::_InitCorners()
426{
427	_SetToWindowCorner(fLeftTopCrossing->RightBottomCorner());
428	_SetToNeighbourCorner(fLeftTopCrossing->LeftBottomCorner());
429	_SetToNeighbourCorner(fLeftTopCrossing->RightTopCorner());
430
431	_SetToWindowCorner(fRightTopCrossing->LeftBottomCorner());
432	_SetToNeighbourCorner(fRightTopCrossing->LeftTopCorner());
433	_SetToNeighbourCorner(fRightTopCrossing->RightBottomCorner());
434
435	_SetToWindowCorner(fLeftBottomCrossing->RightTopCorner());
436	_SetToNeighbourCorner(fLeftBottomCrossing->LeftTopCorner());
437	_SetToNeighbourCorner(fLeftBottomCrossing->RightBottomCorner());
438
439	_SetToWindowCorner(fRightBottomCrossing->LeftTopCorner());
440	_SetToNeighbourCorner(fRightBottomCrossing->LeftBottomCorner());
441	_SetToNeighbourCorner(fRightBottomCrossing->RightTopCorner());
442}
443
444
445void
446WindowArea::_CleanupCorners()
447{
448	_UnsetWindowCorner(fLeftTopCrossing->RightBottomCorner());
449	_UnsetNeighbourCorner(fLeftTopCrossing->LeftBottomCorner(),
450		fLeftBottomCrossing->LeftTopCorner());
451	_UnsetNeighbourCorner(fLeftTopCrossing->RightTopCorner(),
452		fLeftBottomCrossing->LeftTopCorner());
453
454	_UnsetWindowCorner(fRightTopCrossing->LeftBottomCorner());
455	_UnsetNeighbourCorner(fRightTopCrossing->LeftTopCorner(),
456		fLeftBottomCrossing->RightTopCorner());
457	_UnsetNeighbourCorner(fRightTopCrossing->RightBottomCorner(),
458		fLeftBottomCrossing->RightTopCorner());
459
460	_UnsetWindowCorner(fLeftBottomCrossing->RightTopCorner());
461	_UnsetNeighbourCorner(fLeftBottomCrossing->LeftTopCorner(),
462		fLeftBottomCrossing->LeftBottomCorner());
463	_UnsetNeighbourCorner(fLeftBottomCrossing->RightBottomCorner(),
464		fLeftBottomCrossing->LeftBottomCorner());
465
466	_UnsetWindowCorner(fRightBottomCrossing->LeftTopCorner());
467	_UnsetNeighbourCorner(fRightBottomCrossing->LeftBottomCorner(),
468		fRightBottomCrossing->RightBottomCorner());
469	_UnsetNeighbourCorner(fRightBottomCrossing->RightTopCorner(),
470		fRightBottomCrossing->RightBottomCorner());
471}
472
473
474void
475WindowArea::_SetToWindowCorner(Corner* corner)
476{
477	corner->status = Corner::kUsed;
478	corner->windowArea = this;
479}
480
481
482void
483WindowArea::_SetToNeighbourCorner(Corner* neighbour)
484{
485	if (neighbour->status == Corner::kNotDockable)
486		neighbour->status = Corner::kFree;
487}
488
489
490void
491WindowArea::_UnsetWindowCorner(Corner* corner)
492{
493	corner->status = Corner::kFree;
494	corner->windowArea = NULL;
495}
496
497
498void
499WindowArea::_UnsetNeighbourCorner(Corner* neighbour, Corner* opponent)
500{
501	if (neighbour->status == Corner::kFree && opponent->status != Corner::kUsed)
502		neighbour->status = Corner::kNotDockable;
503}
504
505
506void
507WindowArea::_MoveToSAT(SATWindow* triggerWindow)
508{
509	SATWindow* topWindow = TopWindow();
510	// if there is no window in the group we are done
511	if (topWindow == NULL)
512		return;
513
514	BRect frameSAT(LeftVar()->Value() - kMakePositiveOffset,
515		TopVar()->Value() - kMakePositiveOffset,
516		RightVar()->Value() - kMakePositiveOffset,
517		BottomVar()->Value() - kMakePositiveOffset);
518	topWindow->AdjustSizeLimits(frameSAT);
519
520	BRect frame = topWindow->CompleteWindowFrame();
521	float deltaToX = round(frameSAT.left - frame.left);
522	float deltaToY = round(frameSAT.top - frame.top);
523	frame.OffsetBy(deltaToX, deltaToY);
524	float deltaByX = round(frameSAT.right - frame.right);
525	float deltaByY = round(frameSAT.bottom - frame.bottom);
526
527	int32 workspace = triggerWindow->GetWindow()->CurrentWorkspace();
528	Desktop* desktop = triggerWindow->GetWindow()->Desktop();
529	desktop->MoveWindowBy(topWindow->GetWindow(), deltaToX, deltaToY,
530		workspace);
531	// Update frame to the new position
532	desktop->ResizeWindowBy(topWindow->GetWindow(), deltaByX, deltaByY);
533
534	UpdateSizeConstaints(frameSAT);
535}
536
537
538Corner::Corner()
539	:
540	status(kNotDockable),
541	windowArea(NULL)
542{
543
544}
545
546
547void
548Corner::Trace() const
549{
550	switch (status) {
551		case kFree:
552			debug_printf("free corner\n");
553			break;
554
555		case kUsed:
556		{
557			debug_printf("attached windows:\n");
558			const SATWindowList& list = windowArea->WindowList();
559			for (int i = 0; i < list.CountItems(); i++) {
560				debug_printf("- %s\n", list.ItemAt(i)->GetWindow()->Title());
561			}
562			break;
563		}
564
565		case kNotDockable:
566			debug_printf("not dockable\n");
567			break;
568	};
569}
570
571
572Crossing::Crossing(Tab* vertical, Tab* horizontal)
573	:
574	fVerticalTab(vertical),
575	fHorizontalTab(horizontal)
576{
577}
578
579
580Crossing::~Crossing()
581{
582	fVerticalTab->RemoveCrossing(this);
583	fHorizontalTab->RemoveCrossing(this);
584}
585
586
587Corner*
588Crossing::GetCorner(Corner::position_t corner) const
589{
590	return &const_cast<Corner*>(fCorners)[corner];
591}
592
593
594Corner*
595Crossing::GetOppositeCorner(Corner::position_t corner) const
596{
597	return &const_cast<Corner*>(fCorners)[3 - corner];
598}
599
600
601Tab*
602Crossing::VerticalTab() const
603{
604	return fVerticalTab;
605}
606
607
608Tab*
609Crossing::HorizontalTab() const
610{
611	return fHorizontalTab;
612}
613
614
615void
616Crossing::Trace() const
617{
618	debug_printf("left-top corner: ");
619	fCorners[Corner::kLeftTop].Trace();
620	debug_printf("right-top corner: ");
621	fCorners[Corner::kRightTop].Trace();
622	debug_printf("left-bottom corner: ");
623	fCorners[Corner::kLeftBottom].Trace();
624	debug_printf("right-bottom corner: ");
625	fCorners[Corner::kRightBottom].Trace();
626}
627
628
629Tab::Tab(SATGroup* group, Variable* variable, orientation_t orientation)
630	:
631	fGroup(group),
632	fVariable(variable),
633	fOrientation(orientation)
634{
635
636}
637
638
639Tab::~Tab()
640{
641	if (fOrientation == kVertical)
642		fGroup->_RemoveVerticalTab(this);
643	else
644		fGroup->_RemoveHorizontalTab(this);
645
646	delete fVariable;
647}
648
649
650float
651Tab::Position() const
652{
653	return (float)fVariable->Value() - kMakePositiveOffset;
654}
655
656
657void
658Tab::SetPosition(float position)
659{
660	fVariable->SetValue(position + kMakePositiveOffset);
661}
662
663
664Tab::orientation_t
665Tab::Orientation() const
666{
667	return fOrientation;
668}
669
670
671Constraint*
672Tab::Connect(Variable* variable)
673{
674	return fVariable->IsEqual(variable);
675}
676
677
678BReference<Crossing>
679Tab::AddCrossing(Tab* tab)
680{
681	if (tab->Orientation() == fOrientation)
682		return NULL;
683
684	Tab* vTab = (fOrientation == kVertical) ? this : tab;
685	Tab* hTab = (fOrientation == kHorizontal) ? this : tab;
686
687	Crossing* crossing = new (std::nothrow)Crossing(vTab, hTab);
688	if (!crossing)
689		return NULL;
690
691	if (!fCrossingList.AddItem(crossing)) {
692		return NULL;
693	}
694	if (!tab->fCrossingList.AddItem(crossing)) {
695		fCrossingList.RemoveItem(crossing);
696		return NULL;
697	}
698
699	BReference<Crossing> crossingRef(crossing, true);
700	return crossingRef;
701}
702
703
704bool
705Tab::RemoveCrossing(Crossing* crossing)
706{
707	Tab* vTab = crossing->VerticalTab();
708	Tab* hTab = crossing->HorizontalTab();
709
710	if (vTab != this && hTab != this)
711		return false;
712	fCrossingList.RemoveItem(crossing);
713
714	return true;
715}
716
717
718int32
719Tab::FindCrossingIndex(Tab* tab)
720{
721	if (fOrientation == kVertical) {
722		for (int32 i = 0; i < fCrossingList.CountItems(); i++) {
723			if (fCrossingList.ItemAt(i)->HorizontalTab() == tab)
724				return i;
725		}
726	} else {
727		for (int32 i = 0; i < fCrossingList.CountItems(); i++) {
728			if (fCrossingList.ItemAt(i)->VerticalTab() == tab)
729				return i;
730		}
731	}
732	return -1;
733}
734
735
736int32
737Tab::FindCrossingIndex(float pos)
738{
739	if (fOrientation == kVertical) {
740		for (int32 i = 0; i < fCrossingList.CountItems(); i++) {
741			if (fabs(fCrossingList.ItemAt(i)->HorizontalTab()->Position() - pos)
742				< 0.0001)
743				return i;
744		}
745	} else {
746		for (int32 i = 0; i < fCrossingList.CountItems(); i++) {
747			if (fabs(fCrossingList.ItemAt(i)->VerticalTab()->Position() - pos)
748				< 0.0001)
749				return i;
750		}
751	}
752	return -1;
753}
754
755
756Crossing*
757Tab::FindCrossing(Tab* tab)
758{
759	return fCrossingList.ItemAt(FindCrossingIndex(tab));
760}
761
762
763Crossing*
764Tab::FindCrossing(float tabPosition)
765{
766	return fCrossingList.ItemAt(FindCrossingIndex(tabPosition));
767}
768
769
770const CrossingList*
771Tab::GetCrossingList() const
772{
773	return &fCrossingList;
774}
775
776
777int
778Tab::CompareFunction(const Tab* tab1, const Tab* tab2)
779{
780	if (tab1->Position() < tab2->Position())
781		return -1;
782
783	return 1;
784}
785
786
787SATGroup::SATGroup()
788	:
789	fHorizontalTabsSorted(false),
790	fVerticalTabsSorted(false)
791{
792
793}
794
795
796SATGroup::~SATGroup()
797{
798	// Should be empty
799	//while (fSATWindowList.CountItems() > 0)
800	//	RemoveWindow(fSATWindowList.ItemAt(0));
801}
802
803
804bool
805SATGroup::AddWindow(SATWindow* window, Tab* left, Tab* top, Tab* right,
806	Tab* bottom)
807{
808	STRACE_SAT("SATGroup::AddWindow\n");
809
810	// first check if we have to create tabs and missing corners.
811	BReference<Tab> leftRef, rightRef, topRef, bottomRef;
812	BReference<Crossing> leftTopRef, rightTopRef, leftBottomRef, rightBottomRef;
813
814	if (left && top)
815		leftTopRef = left->FindCrossing(top);
816	if (right && top)
817		rightTopRef = right->FindCrossing(top);
818	if (left && bottom)
819		leftBottomRef = left->FindCrossing(bottom);
820	if (right && bottom)
821		rightBottomRef = right->FindCrossing(bottom);
822
823	if (!left) {
824		leftRef = _AddVerticalTab();
825		left = leftRef.Get();
826	}
827	if (!top) {
828		topRef = _AddHorizontalTab();
829		top = topRef.Get();
830	}
831	if (!right) {
832		rightRef = _AddVerticalTab();
833		right = rightRef.Get();
834	}
835	if (!bottom) {
836		bottomRef = _AddHorizontalTab();
837		bottom = bottomRef.Get();
838	}
839	if (!left || !top || !right || !bottom)
840		return false;
841
842	if (!leftTopRef) {
843		leftTopRef = left->AddCrossing(top);
844		if (!leftTopRef)
845			return false;
846	}
847	if (!rightTopRef) {
848		rightTopRef = right->AddCrossing(top);
849		if (!rightTopRef)
850			return false;
851	}
852	if (!leftBottomRef) {
853		leftBottomRef = left->AddCrossing(bottom);
854		if (!leftBottomRef)
855			return false;
856	}
857	if (!rightBottomRef) {
858		rightBottomRef = right->AddCrossing(bottom);
859		if (!rightBottomRef)
860			return false;
861	}
862
863	WindowArea* area = new(std::nothrow) WindowArea(leftTopRef, rightTopRef,
864		leftBottomRef, rightBottomRef);
865	if (!area)
866		return false;
867	// the area register itself in our area list
868	if (area->Init(this) == false) {
869		delete area;
870		return false;
871	}
872	// delete the area if AddWindow failed / release our reference on it
873	BReference<WindowArea> areaRef(area, true);
874
875	return AddWindow(window, area);
876}
877
878
879bool
880SATGroup::AddWindow(SATWindow* window, WindowArea* area, SATWindow* after)
881{
882	if (!area->_AddWindow(window, after))
883		return false;
884
885	if (!fSATWindowList.AddItem(window)) {
886		area->_RemoveWindow(window);
887		return false;
888	}
889
890	if (!window->AddedToGroup(this, area)) {
891		area->_RemoveWindow(window);
892		fSATWindowList.RemoveItem(window);
893		return false;
894	}
895
896	return true;
897}
898
899
900bool
901SATGroup::RemoveWindow(SATWindow* window, bool stayBelowMouse)
902{
903	if (!fSATWindowList.RemoveItem(window))
904		return false;
905
906	// We need the area a little bit longer because the area could hold the
907	// last reference to the group.
908	BReference<WindowArea> area = window->GetWindowArea();
909	if (area.Get() != NULL)
910		area->_RemoveWindow(window);
911
912	window->RemovedFromGroup(this, stayBelowMouse);
913
914	if (CountItems() >= 2)
915		WindowAt(0)->DoGroupLayout();
916
917	return true;
918}
919
920
921int32
922SATGroup::CountItems()
923{
924	return fSATWindowList.CountItems();
925};
926
927
928SATWindow*
929SATGroup::WindowAt(int32 index)
930{
931	return fSATWindowList.ItemAt(index);
932}
933
934
935const TabList*
936SATGroup::HorizontalTabs()
937{
938	if (!fHorizontalTabsSorted) {
939		fHorizontalTabs.SortItems(Tab::CompareFunction);
940		fHorizontalTabsSorted = true;
941	}
942	return &fHorizontalTabs;
943}
944
945
946const TabList*
947SATGroup::VerticalTabs()
948{
949	if (!fVerticalTabsSorted) {
950		fVerticalTabs.SortItems(Tab::CompareFunction);
951		fVerticalTabsSorted = true;
952	}
953	return &fVerticalTabs;
954}
955
956
957Tab*
958SATGroup::FindHorizontalTab(float position)
959{
960	return _FindTab(fHorizontalTabs, position);
961}
962
963
964Tab*
965SATGroup::FindVerticalTab(float position)
966{
967	return _FindTab(fVerticalTabs, position);
968}
969
970
971void
972SATGroup::WindowAreaRemoved(WindowArea* area)
973{
974	_SplitGroupIfNecessary(area);
975}
976
977
978status_t
979SATGroup::RestoreGroup(const BMessage& archive, StackAndTile* sat)
980{
981	// create new group
982	SATGroup* group = new (std::nothrow)SATGroup;
983	if (!group)
984		return B_NO_MEMORY;
985	BReference<SATGroup> groupRef;
986	groupRef.SetTo(group, true);
987
988	int32 nHTabs, nVTabs;
989	status_t status;
990	status = archive.FindInt32("htab_count", &nHTabs);
991	if (status != B_OK)
992		return status;
993	status = archive.FindInt32("vtab_count", &nVTabs);
994	if (status != B_OK)
995		return status;
996
997	vector<BReference<Tab> > tempHTabs;
998	for (int i = 0; i < nHTabs; i++) {
999		BReference<Tab> tab = group->_AddHorizontalTab();
1000		if (!tab)
1001			return B_NO_MEMORY;
1002		tempHTabs.push_back(tab);
1003	}
1004	vector<BReference<Tab> > tempVTabs;
1005	for (int i = 0; i < nVTabs; i++) {
1006		BReference<Tab> tab = group->_AddVerticalTab();
1007		if (!tab)
1008			return B_NO_MEMORY;
1009		tempVTabs.push_back(tab);
1010	}
1011
1012	BMessage areaArchive;
1013	for (int32 i = 0; archive.FindMessage("area", i, &areaArchive) == B_OK;
1014		i++) {
1015		uint32 leftTab, rightTab, topTab, bottomTab;
1016		if (areaArchive.FindInt32("left_tab", (int32*)&leftTab) != B_OK
1017			|| areaArchive.FindInt32("right_tab", (int32*)&rightTab) != B_OK
1018			|| areaArchive.FindInt32("top_tab", (int32*)&topTab) != B_OK
1019			|| areaArchive.FindInt32("bottom_tab", (int32*)&bottomTab) != B_OK)
1020			return B_ERROR;
1021
1022		if (leftTab >= tempVTabs.size() || rightTab >= tempVTabs.size())
1023			return B_BAD_VALUE;
1024		if (topTab >= tempHTabs.size() || bottomTab >= tempHTabs.size())
1025			return B_BAD_VALUE;
1026
1027		Tab* left = tempVTabs[leftTab];
1028		Tab* right = tempVTabs[rightTab];
1029		Tab* top = tempHTabs[topTab];
1030		Tab* bottom = tempHTabs[bottomTab];
1031
1032		// adding windows to area
1033		uint64 windowId;
1034		SATWindow* prevWindow = NULL;
1035		for (int32 i = 0; areaArchive.FindInt64("window", i,
1036			(int64*)&windowId) == B_OK; i++) {
1037			SATWindow* window = sat->FindSATWindow(windowId);
1038			if (!window)
1039				continue;
1040
1041			if (prevWindow == NULL) {
1042				if (!group->AddWindow(window, left, top, right, bottom))
1043					continue;
1044				prevWindow = window;
1045			} else {
1046				if (!prevWindow->StackWindow(window))
1047					continue;
1048				prevWindow = window;
1049			}
1050		}
1051	}
1052	return B_OK;
1053}
1054
1055
1056status_t
1057SATGroup::ArchiveGroup(BMessage& archive)
1058{
1059	archive.AddInt32("htab_count", fHorizontalTabs.CountItems());
1060	archive.AddInt32("vtab_count", fVerticalTabs.CountItems());
1061
1062	for (int i = 0; i < fWindowAreaList.CountItems(); i++) {
1063		WindowArea* area = fWindowAreaList.ItemAt(i);
1064		int32 leftTab = fVerticalTabs.IndexOf(area->LeftTab());
1065		int32 rightTab = fVerticalTabs.IndexOf(area->RightTab());
1066		int32 topTab = fHorizontalTabs.IndexOf(area->TopTab());
1067		int32 bottomTab = fHorizontalTabs.IndexOf(area->BottomTab());
1068
1069		BMessage areaMessage;
1070		areaMessage.AddInt32("left_tab", leftTab);
1071		areaMessage.AddInt32("right_tab", rightTab);
1072		areaMessage.AddInt32("top_tab", topTab);
1073		areaMessage.AddInt32("bottom_tab", bottomTab);
1074
1075		const SATWindowList& windowList = area->WindowList();
1076		for (int a = 0; a < windowList.CountItems(); a++)
1077			areaMessage.AddInt64("window", windowList.ItemAt(a)->Id());
1078
1079		archive.AddMessage("area", &areaMessage);
1080	}
1081	return B_OK;
1082}
1083
1084
1085BReference<Tab>
1086SATGroup::_AddHorizontalTab(float position)
1087{
1088	Variable* variable = fLinearSpec.AddVariable();
1089	if (!variable)
1090		return NULL;
1091
1092	Tab* tab = new (std::nothrow)Tab(this, variable, Tab::kHorizontal);
1093	if (!tab)
1094		return NULL;
1095	BReference<Tab> tabRef(tab, true);
1096
1097	if (!fHorizontalTabs.AddItem(tab))
1098		return NULL;
1099
1100	fHorizontalTabsSorted = false;
1101	tabRef->SetPosition(position);
1102	return tabRef;
1103}
1104
1105
1106BReference<Tab>
1107SATGroup::_AddVerticalTab(float position)
1108{
1109	Variable* variable = fLinearSpec.AddVariable();
1110	if (!variable)
1111		return NULL;
1112
1113	Tab* tab = new (std::nothrow)Tab(this, variable, Tab::kVertical);
1114	if (!tab)
1115		return NULL;
1116	BReference<Tab> tabRef(tab, true);
1117
1118	if (!fVerticalTabs.AddItem(tab))
1119		return NULL;
1120
1121	fVerticalTabsSorted = false;
1122	tabRef->SetPosition(position);
1123	return tabRef;
1124}
1125
1126
1127bool
1128SATGroup::_RemoveHorizontalTab(Tab* tab)
1129{
1130	if (!fHorizontalTabs.RemoveItem(tab))
1131		return false;
1132	fHorizontalTabsSorted = false;
1133	// don't delete the tab it is reference counted
1134	return true;
1135}
1136
1137
1138bool
1139SATGroup::_RemoveVerticalTab(Tab* tab)
1140{
1141	if (!fVerticalTabs.RemoveItem(tab))
1142		return false;
1143	fVerticalTabsSorted = false;
1144	// don't delete the tab it is reference counted
1145	return true;
1146}
1147
1148
1149Tab*
1150SATGroup::_FindTab(const TabList& list, float position)
1151{
1152	for (int i = 0; i < list.CountItems(); i++)
1153		if (fabs(list.ItemAt(i)->Position() - position) < 0.00001)
1154			return list.ItemAt(i);
1155
1156	return NULL;
1157}
1158
1159
1160void
1161SATGroup::_SplitGroupIfNecessary(WindowArea* removedArea)
1162{
1163	// if there are windows stacked in the area we don't need to split
1164	if (!removedArea || removedArea->WindowList().CountItems() > 1)
1165		return;
1166
1167	WindowAreaList neighbourWindows;
1168
1169	_FillNeighbourList(neighbourWindows, removedArea);
1170
1171	bool ownGroupProcessed = false;
1172	WindowAreaList newGroup;
1173	while (_FindConnectedGroup(neighbourWindows, removedArea, newGroup)) {
1174		STRACE_SAT("Connected group found; %i window(s)\n",
1175			(int)newGroup.CountItems());
1176		if (newGroup.CountItems() == 1
1177			&& newGroup.ItemAt(0)->WindowList().CountItems() == 1) {
1178			SATWindow* window = newGroup.ItemAt(0)->WindowList().ItemAt(0);
1179			RemoveWindow(window);
1180			_EnsureGroupIsOnScreen(window->GetGroup());
1181		} else if (ownGroupProcessed)
1182			_SpawnNewGroup(newGroup);
1183		else {
1184			_EnsureGroupIsOnScreen(this);
1185			ownGroupProcessed = true;
1186		}
1187
1188		newGroup.MakeEmpty();
1189	}
1190}
1191
1192
1193void
1194SATGroup::_FillNeighbourList(WindowAreaList& neighbourWindows,
1195	WindowArea* area)
1196{
1197	_LeftNeighbours(neighbourWindows, area);
1198	_RightNeighbours(neighbourWindows, area);
1199	_TopNeighbours(neighbourWindows, area);
1200	_BottomNeighbours(neighbourWindows, area);
1201}
1202
1203
1204void
1205SATGroup::_LeftNeighbours(WindowAreaList& neighbourWindows, WindowArea* parent)
1206{
1207	float startPos = parent->LeftTopCrossing()->HorizontalTab()->Position();
1208	float endPos = parent->LeftBottomCrossing()->HorizontalTab()->Position();
1209
1210	Tab* tab = parent->LeftTopCrossing()->VerticalTab();
1211	const CrossingList* crossingList = tab->GetCrossingList();
1212	for (int i = 0; i < crossingList->CountItems(); i++) {
1213		Corner* corner = crossingList->ItemAt(i)->LeftTopCorner();
1214		if (corner->status != Corner::kUsed)
1215			continue;
1216
1217		WindowArea* area = corner->windowArea;
1218		float pos1 = area->LeftTopCrossing()->HorizontalTab()->Position();
1219		float pos2 = area->LeftBottomCrossing()->HorizontalTab()->Position();
1220
1221		if (pos1 < endPos && pos2 > startPos)
1222			neighbourWindows.AddItem(area);
1223
1224		if (pos2 > endPos)
1225			break;
1226	}
1227}
1228
1229
1230void
1231SATGroup::_TopNeighbours(WindowAreaList& neighbourWindows, WindowArea* parent)
1232{
1233	float startPos = parent->LeftTopCrossing()->VerticalTab()->Position();
1234	float endPos = parent->RightTopCrossing()->VerticalTab()->Position();
1235
1236	Tab* tab = parent->LeftTopCrossing()->HorizontalTab();
1237	const CrossingList* crossingList = tab->GetCrossingList();
1238	for (int i = 0; i < crossingList->CountItems(); i++) {
1239		Corner* corner = crossingList->ItemAt(i)->LeftTopCorner();
1240		if (corner->status != Corner::kUsed)
1241			continue;
1242
1243		WindowArea* area = corner->windowArea;
1244		float pos1 = area->LeftTopCrossing()->VerticalTab()->Position();
1245		float pos2 = area->RightTopCrossing()->VerticalTab()->Position();
1246
1247		if (pos1 < endPos && pos2 > startPos)
1248			neighbourWindows.AddItem(area);
1249
1250		if (pos2 > endPos)
1251			break;
1252	}
1253}
1254
1255
1256void
1257SATGroup::_RightNeighbours(WindowAreaList& neighbourWindows, WindowArea* parent)
1258{
1259	float startPos = parent->RightTopCrossing()->HorizontalTab()->Position();
1260	float endPos = parent->RightBottomCrossing()->HorizontalTab()->Position();
1261
1262	Tab* tab = parent->RightTopCrossing()->VerticalTab();
1263	const CrossingList* crossingList = tab->GetCrossingList();
1264	for (int i = 0; i < crossingList->CountItems(); i++) {
1265		Corner* corner = crossingList->ItemAt(i)->RightTopCorner();
1266		if (corner->status != Corner::kUsed)
1267			continue;
1268
1269		WindowArea* area = corner->windowArea;
1270		float pos1 = area->RightTopCrossing()->HorizontalTab()->Position();
1271		float pos2 = area->RightBottomCrossing()->HorizontalTab()->Position();
1272
1273		if (pos1 < endPos && pos2 > startPos)
1274			neighbourWindows.AddItem(area);
1275
1276		if (pos2 > endPos)
1277			break;
1278	}
1279}
1280
1281
1282void
1283SATGroup::_BottomNeighbours(WindowAreaList& neighbourWindows,
1284	WindowArea* parent)
1285{
1286	float startPos = parent->LeftBottomCrossing()->VerticalTab()->Position();
1287	float endPos = parent->RightBottomCrossing()->VerticalTab()->Position();
1288
1289	Tab* tab = parent->LeftBottomCrossing()->HorizontalTab();
1290	const CrossingList* crossingList = tab->GetCrossingList();
1291	for (int i = 0; i < crossingList->CountItems(); i++) {
1292		Corner* corner = crossingList->ItemAt(i)->LeftBottomCorner();
1293		if (corner->status != Corner::kUsed)
1294			continue;
1295
1296		WindowArea* area = corner->windowArea;
1297		float pos1 = area->LeftBottomCrossing()->VerticalTab()->Position();
1298		float pos2 = area->RightBottomCrossing()->VerticalTab()->Position();
1299
1300		if (pos1 < endPos && pos2 > startPos)
1301			neighbourWindows.AddItem(area);
1302
1303		if (pos2 > endPos)
1304			break;
1305	}
1306}
1307
1308
1309bool
1310SATGroup::_FindConnectedGroup(WindowAreaList& seedList, WindowArea* removedArea,
1311	WindowAreaList& newGroup)
1312{
1313	if (seedList.CountItems() == 0)
1314		return false;
1315
1316	WindowArea* area = seedList.RemoveItemAt(0);
1317	newGroup.AddItem(area);
1318
1319	_FollowSeed(area, removedArea, seedList, newGroup);
1320	return true;
1321}
1322
1323
1324void
1325SATGroup::_FollowSeed(WindowArea* area, WindowArea* veto,
1326	WindowAreaList& seedList, WindowAreaList& newGroup)
1327{
1328	WindowAreaList neighbours;
1329	_FillNeighbourList(neighbours, area);
1330	for (int i = 0; i < neighbours.CountItems(); i++) {
1331		WindowArea* currentArea = neighbours.ItemAt(i);
1332		if (currentArea != veto && !newGroup.HasItem(currentArea)) {
1333			newGroup.AddItem(currentArea);
1334			// if we get a area from the seed list it is not a seed any more
1335			seedList.RemoveItem(currentArea);
1336		}
1337		else {
1338			// don't _FollowSeed of invalid areas
1339			neighbours.RemoveItemAt(i);
1340			i--;
1341		}
1342	}
1343
1344	for (int i = 0; i < neighbours.CountItems(); i++)
1345		_FollowSeed(neighbours.ItemAt(i), veto, seedList, newGroup);
1346}
1347
1348
1349void
1350SATGroup::_SpawnNewGroup(const WindowAreaList& newGroup)
1351{
1352	STRACE_SAT("SATGroup::_SpawnNewGroup\n");
1353	SATGroup* group = new (std::nothrow)SATGroup;
1354	if (!group)
1355		return;
1356	BReference<SATGroup> groupRef;
1357	groupRef.SetTo(group, true);
1358
1359	for (int i = 0; i < newGroup.CountItems(); i++)
1360		newGroup.ItemAt(i)->PropagateToGroup(group);
1361
1362	_EnsureGroupIsOnScreen(group);
1363}
1364
1365
1366const float kMinOverlap = 50;
1367const float kMoveToScreen = 75;
1368
1369
1370void
1371SATGroup::_EnsureGroupIsOnScreen(SATGroup* group)
1372{
1373	STRACE_SAT("SATGroup::_EnsureGroupIsOnScreen\n");
1374	if (!group)
1375		return;
1376
1377	if (group->CountItems() < 1)
1378		return;
1379
1380	SATWindow* window = group->WindowAt(0);
1381	Desktop* desktop = window->GetWindow()->Desktop();
1382	if (!desktop)
1383		return;
1384
1385	const float kBigDistance = 1E+10;
1386
1387	float minLeftDistance = kBigDistance;
1388	BRect leftRect;
1389	float minTopDistance = kBigDistance;
1390	BRect topRect;
1391	float minRightDistance = kBigDistance;
1392	BRect rightRect;
1393	float minBottomDistance = kBigDistance;
1394	BRect bottomRect;
1395
1396	BRect screen = window->GetWindow()->Screen()->Frame();
1397	BRect reducedScreen = screen;
1398	reducedScreen.InsetBy(kMinOverlap, kMinOverlap);
1399
1400	for (int i = 0; i < group->CountItems(); i++) {
1401		SATWindow* window = group->WindowAt(i);
1402		BRect frame = window->CompleteWindowFrame();
1403		if (reducedScreen.Intersects(frame))
1404			return;
1405
1406		if (frame.right < screen.left + kMinOverlap) {
1407			float dist = fabs(screen.left - frame.right);
1408			if (dist < minLeftDistance) {
1409				minLeftDistance = dist;
1410				leftRect = frame;
1411			}
1412			else if (dist == minLeftDistance)
1413				leftRect = leftRect | frame;
1414		}
1415		if (frame.top > screen.bottom - kMinOverlap) {
1416			float dist = fabs(frame.top - screen.bottom);
1417			if (dist < minBottomDistance) {
1418				minBottomDistance = dist;
1419				bottomRect = frame;
1420			}
1421			else if (dist == minBottomDistance)
1422				bottomRect = bottomRect | frame;
1423		}
1424		if (frame.left > screen.right - kMinOverlap) {
1425			float dist = fabs(frame.left - screen.right);
1426			if (dist < minRightDistance) {
1427				minRightDistance = dist;
1428				rightRect = frame;
1429			}
1430			else if (dist == minRightDistance)
1431				rightRect = rightRect | frame;
1432		}
1433		if (frame.bottom < screen.top + kMinOverlap) {
1434			float dist = fabs(frame.bottom - screen.top);
1435			if (dist < minTopDistance) {
1436				minTopDistance = dist;
1437				topRect = frame;
1438			}
1439			else if (dist == minTopDistance)
1440				topRect = topRect | frame;
1441		}
1442	}
1443
1444	BPoint offset;
1445	if (minLeftDistance < kBigDistance) {
1446		offset.x = screen.left - leftRect.right + kMoveToScreen;
1447		_CallculateYOffset(offset, leftRect, screen);
1448	}
1449	else if (minTopDistance < kBigDistance) {
1450		offset.y = screen.top - topRect.bottom + kMoveToScreen;
1451		_CallculateXOffset(offset, topRect, screen);
1452	}
1453	else if (minRightDistance < kBigDistance) {
1454		offset.x = screen.right - rightRect.left - kMoveToScreen;
1455		_CallculateYOffset(offset, rightRect, screen);
1456	}
1457	else if (minBottomDistance < kBigDistance) {
1458		offset.y = screen.bottom - bottomRect.top - kMoveToScreen;
1459		_CallculateXOffset(offset, bottomRect, screen);
1460	}
1461
1462	if (offset.x == 0. && offset.y == 0.)
1463		return;
1464	STRACE_SAT("move group back to screen: offset x: %f offset y: %f\n",
1465		offset.x, offset.y);
1466
1467	desktop->MoveWindowBy(window->GetWindow(), offset.x, offset.y);
1468	window->DoGroupLayout();
1469}
1470
1471
1472void
1473SATGroup::_CallculateXOffset(BPoint& offset, BRect& frame, BRect& screen)
1474{
1475	if (frame.right < screen.left + kMinOverlap)
1476		offset.x = screen.left - frame.right + kMoveToScreen;
1477	else if (frame.left > screen.right - kMinOverlap)
1478		offset.x = screen.right - frame.left - kMoveToScreen;
1479}
1480
1481
1482void
1483SATGroup::_CallculateYOffset(BPoint& offset, BRect& frame, BRect& screen)
1484{
1485	if (frame.top > screen.bottom - kMinOverlap)
1486		offset.y = screen.bottom - frame.top - kMoveToScreen;
1487	else if (frame.bottom < screen.top + kMinOverlap)
1488		offset.y = screen.top - frame.bottom + kMoveToScreen;
1489}
1490