1/*
2 * Copyright 2001-2013 Haiku, Inc. All rights reserved.
3 * Distributed under the terms of the MIT License.
4 *
5 * Authors:
6 *		Marc Flerackers (mflerackers@androme.be)
7 *		Axel D��rfler, axeld@pinc-software.de
8 *		Rene Gollent (rene@gollent.com)
9 *		Philippe Saint-Pierre, stpere@gmail.com
10 *		John Scipione, jscipione@gmail.com
11 */
12
13
14//! BOutlineListView represents a "nestable" list view.
15
16
17#include <OutlineListView.h>
18
19#include <algorithm>
20
21#include <stdio.h>
22#include <stdlib.h>
23
24#include <ControlLook.h>
25#include <Window.h>
26
27#include <binary_compatibility/Interface.h>
28
29
30typedef int (*compare_func)(const BListItem* a, const BListItem* b);
31
32
33struct ListItemComparator {
34	ListItemComparator(compare_func compareFunc)
35		:
36		fCompareFunc(compareFunc)
37	{
38	}
39
40	bool operator()(const BListItem* a, const BListItem* b) const
41	{
42		return fCompareFunc(a, b) < 0;
43	}
44
45private:
46	compare_func	fCompareFunc;
47};
48
49
50static void
51_GetSubItems(BList& sourceList, BList& destList, BListItem* parent, int32 start)
52{
53	for (int32 i = start; i < sourceList.CountItems(); i++) {
54		BListItem* item = (BListItem*)sourceList.ItemAt(i);
55		if (item->OutlineLevel() <= parent->OutlineLevel())
56			break;
57		destList.AddItem(item);
58	}
59}
60
61
62static void
63_DoSwap(BList& list, int32 firstIndex, int32 secondIndex, BList* firstItems,
64	BList* secondItems)
65{
66	BListItem* item = (BListItem*)list.ItemAt(firstIndex);
67	list.SwapItems(firstIndex, secondIndex);
68	list.RemoveItems(secondIndex + 1, secondItems->CountItems());
69	list.RemoveItems(firstIndex + 1, firstItems->CountItems());
70	list.AddList(secondItems, firstIndex + 1);
71	int32 newIndex = list.IndexOf(item);
72	if (newIndex + 1 < list.CountItems())
73		list.AddList(firstItems, newIndex + 1);
74	else
75		list.AddList(firstItems);
76}
77
78
79//	#pragma mark - BOutlineListView
80
81
82BOutlineListView::BOutlineListView(BRect frame, const char* name,
83	list_view_type type, uint32 resizingMode, uint32 flags)
84	:
85	BListView(frame, name, type, resizingMode, flags)
86{
87}
88
89
90BOutlineListView::BOutlineListView(const char* name, list_view_type type,
91	uint32 flags)
92	:
93	BListView(name, type, flags)
94{
95}
96
97
98BOutlineListView::BOutlineListView(BMessage* archive)
99	:
100	BListView(archive)
101{
102	int32 i = 0;
103	BMessage subData;
104	while (archive->FindMessage("_l_full_items", i++, &subData) == B_OK) {
105		BArchivable* object = instantiate_object(&subData);
106		if (!object)
107			continue;
108
109		BListItem* item = dynamic_cast<BListItem*>(object);
110		if (item)
111			AddItem(item);
112	}
113}
114
115
116BOutlineListView::~BOutlineListView()
117{
118	fFullList.MakeEmpty();
119}
120
121
122BArchivable*
123BOutlineListView::Instantiate(BMessage* archive)
124{
125	if (validate_instantiation(archive, "BOutlineListView"))
126		return new BOutlineListView(archive);
127
128	return NULL;
129}
130
131
132status_t
133BOutlineListView::Archive(BMessage* archive, bool deep) const
134{
135	// Note: We can't call the BListView Archive function here, as we are also
136	// interested in subitems BOutlineListView can have. They are even stored
137	// with a different field name (_l_full_items vs. _l_items).
138
139	status_t status = BView::Archive(archive, deep);
140	if (status != B_OK)
141		return status;
142
143	status = archive->AddInt32("_lv_type", fListType);
144	if (status == B_OK && deep) {
145		int32 i = 0;
146		BListItem* item = NULL;
147		while ((item = static_cast<BListItem*>(fFullList.ItemAt(i++)))) {
148			BMessage subData;
149			status = item->Archive(&subData, true);
150			if (status >= B_OK)
151				status = archive->AddMessage("_l_full_items", &subData);
152
153			if (status < B_OK)
154				break;
155		}
156	}
157
158	if (status >= B_OK && InvocationMessage() != NULL)
159		status = archive->AddMessage("_msg", InvocationMessage());
160
161	if (status == B_OK && fSelectMessage != NULL)
162		status = archive->AddMessage("_2nd_msg", fSelectMessage);
163
164	return status;
165}
166
167
168void
169BOutlineListView::MouseDown(BPoint where)
170{
171	MakeFocus();
172
173	int32 index = IndexOf(where);
174
175	if (index != -1) {
176		BListItem* item = ItemAt(index);
177
178		if (item->fHasSubitems
179			&& LatchRect(ItemFrame(index), item->fLevel).Contains(where)) {
180			if (item->IsExpanded())
181				Collapse(item);
182			else
183				Expand(item);
184		} else
185			BListView::MouseDown(where);
186	}
187}
188
189
190void
191BOutlineListView::KeyDown(const char* bytes, int32 numBytes)
192{
193	if (numBytes == 1) {
194		int32 currentSel = CurrentSelection();
195		switch (bytes[0]) {
196			case B_RIGHT_ARROW:
197			{
198				BListItem* item = ItemAt(currentSel);
199				if (item && item->fHasSubitems) {
200					if (!item->IsExpanded())
201						Expand(item);
202					else {
203						Select(currentSel + 1);
204						ScrollToSelection();
205					}
206				}
207				return;
208			}
209
210			case B_LEFT_ARROW:
211			{
212				BListItem* item = ItemAt(currentSel);
213				if (item) {
214					if (item->fHasSubitems && item->IsExpanded())
215						Collapse(item);
216					else {
217						item = Superitem(item);
218						if (item) {
219							Select(IndexOf(item));
220							ScrollToSelection();
221						}
222					}
223				}
224				return;
225			}
226		}
227	}
228
229	BListView::KeyDown(bytes, numBytes);
230}
231
232
233void
234BOutlineListView::FrameMoved(BPoint newPosition)
235{
236	BListView::FrameMoved(newPosition);
237}
238
239
240void
241BOutlineListView::FrameResized(float newWidth, float newHeight)
242{
243	BListView::FrameResized(newWidth, newHeight);
244}
245
246
247void
248BOutlineListView::MouseUp(BPoint where)
249{
250	BListView::MouseUp(where);
251}
252
253
254bool
255BOutlineListView::AddUnder(BListItem* item, BListItem* superItem)
256{
257	if (superItem == NULL)
258		return AddItem(item);
259
260	fFullList.AddItem(item, FullListIndexOf(superItem) + 1);
261
262	item->fLevel = superItem->OutlineLevel() + 1;
263	superItem->fHasSubitems = true;
264
265	if (superItem->IsItemVisible() && superItem->IsExpanded()) {
266		item->SetItemVisible(true);
267
268		int32 index = BListView::IndexOf(superItem);
269
270		BListView::AddItem(item, index + 1);
271		Invalidate(LatchRect(ItemFrame(index), superItem->OutlineLevel()));
272	} else
273		item->SetItemVisible(false);
274
275	return true;
276}
277
278
279bool
280BOutlineListView::AddItem(BListItem* item)
281{
282	return AddItem(item, FullListCountItems());
283}
284
285
286bool
287BOutlineListView::AddItem(BListItem* item, int32 fullListIndex)
288{
289	if (fullListIndex < 0)
290		fullListIndex = 0;
291	else if (fullListIndex > FullListCountItems())
292		fullListIndex = FullListCountItems();
293
294	if (!fFullList.AddItem(item, fullListIndex))
295		return false;
296
297	// Check if this item is visible, and if it is, add it to the
298	// other list, too
299
300	if (item->fLevel > 0) {
301		BListItem* super = _SuperitemForIndex(fullListIndex, item->fLevel);
302		if (super == NULL)
303			return true;
304
305		bool hadSubitems = super->fHasSubitems;
306		super->fHasSubitems = true;
307
308		if (!super->IsItemVisible() || !super->IsExpanded()) {
309			item->SetItemVisible(false);
310			return true;
311		}
312
313		if (!hadSubitems) {
314			Invalidate(LatchRect(ItemFrame(IndexOf(super)),
315				super->OutlineLevel()));
316		}
317	}
318
319	int32 listIndex = _FindPreviousVisibleIndex(fullListIndex);
320
321	if (!BListView::AddItem(item, IndexOf(FullListItemAt(listIndex)) + 1)) {
322		// adding didn't work out, we need to remove it from the main list again
323		fFullList.RemoveItem(fullListIndex);
324		return false;
325	}
326
327	return true;
328}
329
330
331bool
332BOutlineListView::AddList(BList* newItems)
333{
334	return AddList(newItems, FullListCountItems());
335}
336
337
338bool
339BOutlineListView::AddList(BList* newItems, int32 fullListIndex)
340{
341	if ((newItems == NULL) || (newItems->CountItems() == 0))
342		return false;
343
344	for (int32 i = 0; i < newItems->CountItems(); i++)
345		AddItem((BListItem*)newItems->ItemAt(i), fullListIndex + i);
346
347	return true;
348}
349
350
351bool
352BOutlineListView::RemoveItem(BListItem* item)
353{
354	return _RemoveItem(item, FullListIndexOf(item)) != NULL;
355}
356
357
358BListItem*
359BOutlineListView::RemoveItem(int32 fullListIndex)
360{
361	return _RemoveItem(FullListItemAt(fullListIndex), fullListIndex);
362}
363
364
365bool
366BOutlineListView::RemoveItems(int32 fullListIndex, int32 count)
367{
368	if (fullListIndex >= FullListCountItems())
369		fullListIndex = -1;
370	if (fullListIndex < 0)
371		return false;
372
373	// TODO: very bad for performance!!
374	while (count--)
375		BOutlineListView::RemoveItem(fullListIndex);
376
377	return true;
378}
379
380
381BListItem*
382BOutlineListView::FullListItemAt(int32 fullListIndex) const
383{
384	return (BListItem*)fFullList.ItemAt(fullListIndex);
385}
386
387
388int32
389BOutlineListView::FullListIndexOf(BPoint where) const
390{
391	int32 index = BListView::IndexOf(where);
392
393	if (index > 0)
394		index = _FullListIndex(index);
395
396	return index;
397}
398
399
400int32
401BOutlineListView::FullListIndexOf(BListItem* item) const
402{
403	return fFullList.IndexOf(item);
404}
405
406
407BListItem*
408BOutlineListView::FullListFirstItem() const
409{
410	return (BListItem*)fFullList.FirstItem();
411}
412
413
414BListItem*
415BOutlineListView::FullListLastItem() const
416{
417	return (BListItem*)fFullList.LastItem();
418}
419
420
421bool
422BOutlineListView::FullListHasItem(BListItem* item) const
423{
424	return fFullList.HasItem(item);
425}
426
427
428int32
429BOutlineListView::FullListCountItems() const
430{
431	return fFullList.CountItems();
432}
433
434
435int32
436BOutlineListView::FullListCurrentSelection(int32 index) const
437{
438	int32 i = BListView::CurrentSelection(index);
439
440	BListItem* item = BListView::ItemAt(i);
441	if (item)
442		return fFullList.IndexOf(item);
443
444	return -1;
445}
446
447
448void
449BOutlineListView::MakeEmpty()
450{
451	fFullList.MakeEmpty();
452	BListView::MakeEmpty();
453}
454
455
456bool
457BOutlineListView::FullListIsEmpty() const
458{
459	return fFullList.IsEmpty();
460}
461
462
463void
464BOutlineListView::FullListDoForEach(bool(*func)(BListItem* item))
465{
466	fFullList.DoForEach(reinterpret_cast<bool (*)(void*)>(func));
467}
468
469
470void
471BOutlineListView::FullListDoForEach(bool (*func)(BListItem* item, void* arg),
472	void* arg)
473{
474	fFullList.DoForEach(reinterpret_cast<bool (*)(void*, void*)>(func), arg);
475}
476
477
478BListItem*
479BOutlineListView::Superitem(const BListItem* item)
480{
481	int32 index = FullListIndexOf((BListItem*)item);
482	if (index == -1)
483		return NULL;
484
485	return _SuperitemForIndex(index, item->OutlineLevel());
486}
487
488
489void
490BOutlineListView::Expand(BListItem* item)
491{
492	ExpandOrCollapse(item, true);
493}
494
495
496void
497BOutlineListView::Collapse(BListItem* item)
498{
499	ExpandOrCollapse(item, false);
500}
501
502
503bool
504BOutlineListView::IsExpanded(int32 fullListIndex)
505{
506	BListItem* item = FullListItemAt(fullListIndex);
507	if (!item)
508		return false;
509
510	return item->IsExpanded();
511}
512
513
514BHandler*
515BOutlineListView::ResolveSpecifier(BMessage* message, int32 index,
516	BMessage* specifier, int32 what, const char* property)
517{
518	return BListView::ResolveSpecifier(message, index, specifier, what,
519		property);
520}
521
522
523status_t
524BOutlineListView::GetSupportedSuites(BMessage* data)
525{
526	return BListView::GetSupportedSuites(data);
527}
528
529
530status_t
531BOutlineListView::Perform(perform_code code, void* _data)
532{
533	switch (code) {
534		case PERFORM_CODE_MIN_SIZE:
535			((perform_data_min_size*)_data)->return_value
536				= BOutlineListView::MinSize();
537			return B_OK;
538		case PERFORM_CODE_MAX_SIZE:
539			((perform_data_max_size*)_data)->return_value
540				= BOutlineListView::MaxSize();
541			return B_OK;
542		case PERFORM_CODE_PREFERRED_SIZE:
543			((perform_data_preferred_size*)_data)->return_value
544				= BOutlineListView::PreferredSize();
545			return B_OK;
546		case PERFORM_CODE_LAYOUT_ALIGNMENT:
547			((perform_data_layout_alignment*)_data)->return_value
548				= BOutlineListView::LayoutAlignment();
549			return B_OK;
550		case PERFORM_CODE_HAS_HEIGHT_FOR_WIDTH:
551			((perform_data_has_height_for_width*)_data)->return_value
552				= BOutlineListView::HasHeightForWidth();
553			return B_OK;
554		case PERFORM_CODE_GET_HEIGHT_FOR_WIDTH:
555		{
556			perform_data_get_height_for_width* data
557				= (perform_data_get_height_for_width*)_data;
558			BOutlineListView::GetHeightForWidth(data->width, &data->min,
559				&data->max, &data->preferred);
560			return B_OK;
561		}
562		case PERFORM_CODE_SET_LAYOUT:
563		{
564			perform_data_set_layout* data = (perform_data_set_layout*)_data;
565			BOutlineListView::SetLayout(data->layout);
566			return B_OK;
567		}
568		case PERFORM_CODE_LAYOUT_INVALIDATED:
569		{
570			perform_data_layout_invalidated* data
571				= (perform_data_layout_invalidated*)_data;
572			BOutlineListView::LayoutInvalidated(data->descendants);
573			return B_OK;
574		}
575		case PERFORM_CODE_DO_LAYOUT:
576		{
577			BOutlineListView::DoLayout();
578			return B_OK;
579		}
580	}
581
582	return BListView::Perform(code, _data);
583}
584
585
586void
587BOutlineListView::ResizeToPreferred()
588{
589	BListView::ResizeToPreferred();
590}
591
592
593void
594BOutlineListView::GetPreferredSize(float* _width, float* _height)
595{
596	int32 count = CountItems();
597
598	if (count > 0) {
599		float maxWidth = 0.0;
600		for (int32 i = 0; i < count; i++) {
601			// The item itself does not take his OutlineLevel into account, so
602			// we must make up for that. Also add space for the latch.
603			float itemWidth = ItemAt(i)->Width() + be_plain_font->Size()
604				+ (ItemAt(i)->OutlineLevel() + 1)
605					* be_control_look->DefaultItemSpacing();
606			if (itemWidth > maxWidth)
607				maxWidth = itemWidth;
608		}
609
610		if (_width != NULL)
611			*_width = maxWidth;
612		if (_height != NULL)
613			*_height = ItemAt(count - 1)->Bottom();
614	} else
615		BView::GetPreferredSize(_width, _height);
616}
617
618
619void
620BOutlineListView::MakeFocus(bool state)
621{
622	BListView::MakeFocus(state);
623}
624
625
626void
627BOutlineListView::AllAttached()
628{
629	BListView::AllAttached();
630}
631
632
633void
634BOutlineListView::AllDetached()
635{
636	BListView::AllDetached();
637}
638
639
640void
641BOutlineListView::DetachedFromWindow()
642{
643	BListView::DetachedFromWindow();
644}
645
646
647void
648BOutlineListView::FullListSortItems(int (*compareFunc)(const BListItem* a,
649	const BListItem* b))
650{
651	SortItemsUnder(NULL, false, compareFunc);
652}
653
654
655void
656BOutlineListView::SortItemsUnder(BListItem* superItem, bool oneLevelOnly,
657	int (*compareFunc)(const BListItem* a, const BListItem* b))
658{
659	// This method is quite complicated: basically, it creates a real tree
660	// from the items of the full list, sorts them as needed, and then
661	// populates the entries back into the full and display lists
662
663	int32 firstIndex = FullListIndexOf(superItem) + 1;
664	int32 lastIndex = firstIndex;
665	BList* tree = _BuildTree(superItem, lastIndex);
666
667	_SortTree(tree, oneLevelOnly, compareFunc);
668
669	// Populate to the full list
670	_PopulateTree(tree, fFullList, firstIndex, false);
671
672	if (superItem == NULL
673		|| (superItem->IsItemVisible() && superItem->IsExpanded())) {
674		// Populate to BListView's list
675		firstIndex = fList.IndexOf(superItem) + 1;
676		lastIndex = firstIndex;
677		_PopulateTree(tree, fList, lastIndex, true);
678
679		if (fFirstSelected != -1) {
680			// update selection hints
681			fFirstSelected = _CalcFirstSelected(0);
682			fLastSelected = _CalcLastSelected(CountItems());
683		}
684
685		// only invalidate what may have changed
686		_RecalcItemTops(firstIndex);
687		BRect top = ItemFrame(firstIndex);
688		BRect bottom = ItemFrame(lastIndex - 1);
689		BRect update(top.left, top.top, bottom.right, bottom.bottom);
690		Invalidate(update);
691	}
692
693	_DestructTree(tree);
694}
695
696
697int32
698BOutlineListView::CountItemsUnder(BListItem* superItem, bool oneLevelOnly) const
699{
700	int32 i = 0;
701	uint32 baseLevel = 0;
702	if (_ItemsUnderSetup(superItem, i, baseLevel) != B_OK)
703		return 0;
704
705	int32 count = 0;
706	for (; i < FullListCountItems(); i++) {
707		BListItem* item = FullListItemAt(i);
708
709		// If we jump out of the subtree, return count
710		if (item->fLevel < baseLevel)
711			return count;
712
713		// If the level matches, increase count
714		if (!oneLevelOnly || item->fLevel == baseLevel)
715			count++;
716	}
717
718	return count;
719}
720
721
722BListItem*
723BOutlineListView::EachItemUnder(BListItem* superItem, bool oneLevelOnly,
724	BListItem* (*eachFunc)(BListItem* item, void* arg), void* arg)
725{
726	int32 i = 0;
727	uint32 baseLevel = 0;
728	if (_ItemsUnderSetup(superItem, i, baseLevel) != B_OK)
729		return NULL;
730
731	while (i < FullListCountItems()) {
732		BListItem* item = FullListItemAt(i);
733
734		// If we jump out of the subtree, return NULL
735		if (item->fLevel < baseLevel)
736			return NULL;
737
738		// If the level matches, check the index
739		if (!oneLevelOnly || item->fLevel == baseLevel) {
740			item = eachFunc(item, arg);
741			if (item != NULL)
742				return item;
743		}
744
745		i++;
746	}
747
748	return NULL;
749}
750
751
752BListItem*
753BOutlineListView::ItemUnderAt(BListItem* superItem, bool oneLevelOnly,
754	int32 index) const
755{
756	int32 i = 0;
757	uint32 baseLevel = 0;
758	if (_ItemsUnderSetup(superItem, i, baseLevel) != B_OK)
759		return NULL;
760
761	while (i < FullListCountItems()) {
762		BListItem* item = FullListItemAt(i);
763
764		// If we jump out of the subtree, return NULL
765		if (item->fLevel < baseLevel)
766			return NULL;
767
768		// If the level matches, check the index
769		if (!oneLevelOnly || item->fLevel == baseLevel) {
770			if (index == 0)
771				return item;
772
773			index--;
774		}
775
776		i++;
777	}
778
779	return NULL;
780}
781
782
783bool
784BOutlineListView::DoMiscellaneous(MiscCode code, MiscData* data)
785{
786	if (code == B_SWAP_OP)
787		return _SwapItems(data->swap.a, data->swap.b);
788
789	return BListView::DoMiscellaneous(code, data);
790}
791
792
793void
794BOutlineListView::MessageReceived(BMessage* msg)
795{
796	BListView::MessageReceived(msg);
797}
798
799
800void BOutlineListView::_ReservedOutlineListView1() {}
801void BOutlineListView::_ReservedOutlineListView2() {}
802void BOutlineListView::_ReservedOutlineListView3() {}
803void BOutlineListView::_ReservedOutlineListView4() {}
804
805
806void
807BOutlineListView::ExpandOrCollapse(BListItem* item, bool expand)
808{
809	if (item->IsExpanded() == expand || !FullListHasItem(item))
810		return;
811
812	item->fExpanded = expand;
813
814	// TODO: merge these cases together, they are pretty similar
815
816	if (expand) {
817		uint32 level = item->fLevel;
818		int32 fullListIndex = FullListIndexOf(item);
819		int32 index = IndexOf(item) + 1;
820		int32 startIndex = index;
821		int32 count = FullListCountItems() - fullListIndex - 1;
822		BListItem** items = (BListItem**)fFullList.Items() + fullListIndex + 1;
823
824		BFont font;
825		GetFont(&font);
826		while (count-- > 0) {
827			item = items[0];
828			if (item->fLevel <= level)
829				break;
830
831			if (!item->IsItemVisible()) {
832				// fix selection hints
833				if (index <= fFirstSelected)
834					fFirstSelected++;
835				if (index <= fLastSelected)
836					fLastSelected++;
837
838				fList.AddItem(item, index++);
839				item->Update(this, &font);
840				item->SetItemVisible(true);
841			}
842
843			if (item->HasSubitems() && !item->IsExpanded()) {
844				// Skip hidden children
845				uint32 subLevel = item->fLevel;
846				items++;
847
848				while (count > 0 && items[0]->fLevel > subLevel) {
849					items++;
850					count--;
851				}
852			} else
853				items++;
854		}
855		_RecalcItemTops(startIndex);
856	} else {
857		// collapse
858		const uint32 level = item->fLevel;
859		const int32 fullListIndex = FullListIndexOf(item);
860		const int32 index = IndexOf(item);
861		int32 max = FullListCountItems() - fullListIndex - 1;
862		int32 count = 0;
863		bool selectionChanged = false;
864
865		BListItem** items = (BListItem**)fFullList.Items() + fullListIndex + 1;
866
867		while (max-- > 0) {
868			item = items[0];
869			if (item->fLevel <= level)
870				break;
871
872			if (item->IsItemVisible()) {
873				fList.RemoveItem(item);
874				item->SetItemVisible(false);
875				if (item->IsSelected()) {
876					selectionChanged = true;
877					item->Deselect();
878				}
879				count++;
880			}
881
882			items++;
883		}
884
885		_RecalcItemTops(index);
886		// fix selection hints
887		// if the selected item was just removed by collapsing, select its
888		// parent
889		if (selectionChanged) {
890			if (fFirstSelected > index && fFirstSelected <= index + count) {
891					fFirstSelected = index;
892			}
893			if (fLastSelected > index && fLastSelected <= index + count) {
894				fLastSelected = index;
895			}
896		}
897		if (index + count < fFirstSelected) {
898				// all items removed were higher than the selection range,
899				// adjust the indexes to correspond to their new visible positions
900				fFirstSelected -= count;
901				fLastSelected -= count;
902		}
903
904		int32 maxIndex = fList.CountItems() - 1;
905		if (fFirstSelected > maxIndex)
906			fFirstSelected = maxIndex;
907
908		if (fLastSelected > maxIndex)
909			fLastSelected = maxIndex;
910
911		if (selectionChanged)
912			Select(fFirstSelected, fLastSelected);
913	}
914
915	_FixupScrollBar();
916	Invalidate();
917}
918
919
920BRect
921BOutlineListView::LatchRect(BRect itemRect, int32 level) const
922{
923	float latchWidth = be_plain_font->Size();
924	float latchHeight = be_plain_font->Size();
925	float indentOffset = level * be_control_look->DefaultItemSpacing();
926	float heightOffset = itemRect.Height() / 2 - latchHeight / 2;
927
928	return BRect(0, 0, latchWidth, latchHeight)
929		.OffsetBySelf(itemRect.left, itemRect.top)
930		.OffsetBySelf(indentOffset, heightOffset);
931}
932
933
934void
935BOutlineListView::DrawLatch(BRect itemRect, int32 level, bool collapsed,
936	bool highlighted, bool misTracked)
937{
938	BRect latchRect(LatchRect(itemRect, level));
939	rgb_color base = ui_color(B_PANEL_BACKGROUND_COLOR);
940	int32 arrowDirection = collapsed ? BControlLook::B_RIGHT_ARROW
941		: BControlLook::B_DOWN_ARROW;
942
943	float tintColor = B_DARKEN_4_TINT;
944	if (base.red + base.green + base.blue <= 128 * 3) {
945		tintColor = B_LIGHTEN_2_TINT;
946	}
947
948	be_control_look->DrawArrowShape(this, latchRect, itemRect, base,
949		arrowDirection, 0, tintColor);
950}
951
952
953void
954BOutlineListView::DrawItem(BListItem* item, BRect itemRect, bool complete)
955{
956	if (item->fHasSubitems) {
957		DrawLatch(itemRect, item->fLevel, !item->IsExpanded(),
958			item->IsSelected() || complete, false);
959	}
960
961	itemRect.left += LatchRect(itemRect, item->fLevel).right;
962	BListView::DrawItem(item, itemRect, complete);
963}
964
965
966int32
967BOutlineListView::_FullListIndex(int32 index) const
968{
969	BListItem* item = ItemAt(index);
970
971	if (item == NULL)
972		return -1;
973
974	return FullListIndexOf(item);
975}
976
977
978void
979BOutlineListView::_PopulateTree(BList* tree, BList& target,
980	int32& firstIndex, bool onlyVisible)
981{
982	BListItem** items = (BListItem**)target.Items();
983	int32 count = tree->CountItems();
984
985	for (int32 index = 0; index < count; index++) {
986		BListItem* item = (BListItem*)tree->ItemAtFast(index);
987
988		items[firstIndex++] = item;
989
990		if (item->HasSubitems() && (!onlyVisible || item->IsExpanded())) {
991			_PopulateTree(item->fTemporaryList, target, firstIndex,
992				onlyVisible);
993		}
994	}
995}
996
997
998void
999BOutlineListView::_SortTree(BList* tree, bool oneLevelOnly,
1000	int (*compareFunc)(const BListItem* a, const BListItem* b))
1001{
1002	BListItem** items = (BListItem**)tree->Items();
1003	std::sort(items, items + tree->CountItems(),
1004		ListItemComparator(compareFunc));
1005
1006	if (oneLevelOnly)
1007		return;
1008
1009	for (int32 index = tree->CountItems(); index-- > 0;) {
1010		BListItem* item = (BListItem*)tree->ItemAt(index);
1011
1012		if (item->HasSubitems())
1013			_SortTree(item->fTemporaryList, false, compareFunc);
1014	}
1015}
1016
1017
1018void
1019BOutlineListView::_DestructTree(BList* tree)
1020{
1021	for (int32 index = tree->CountItems(); index-- > 0;) {
1022		BListItem* item = (BListItem*)tree->ItemAt(index);
1023
1024		if (item->HasSubitems())
1025			_DestructTree(item->fTemporaryList);
1026	}
1027
1028	delete tree;
1029}
1030
1031
1032BList*
1033BOutlineListView::_BuildTree(BListItem* superItem, int32& fullListIndex)
1034{
1035	int32 fullCount = FullListCountItems();
1036	uint32 level = superItem != NULL ? superItem->OutlineLevel() + 1 : 0;
1037	BList* list = new BList;
1038	if (superItem != NULL)
1039		superItem->fTemporaryList = list;
1040
1041	while (fullListIndex < fullCount) {
1042		BListItem* item = FullListItemAt(fullListIndex);
1043
1044		// If we jump out of the subtree, break out
1045		if (item->fLevel < level)
1046			break;
1047
1048		// If the level matches, put them into the list
1049		// (we handle the case of a missing sublevel gracefully)
1050		list->AddItem(item);
1051		fullListIndex++;
1052
1053		if (item->HasSubitems()) {
1054			// we're going deeper
1055			_BuildTree(item, fullListIndex);
1056		}
1057	}
1058
1059	return list;
1060}
1061
1062
1063void
1064BOutlineListView::_CullInvisibleItems(BList& list)
1065{
1066	int32 index = 0;
1067	while (index < list.CountItems()) {
1068		if (reinterpret_cast<BListItem*>(list.ItemAt(index))->IsItemVisible())
1069			++index;
1070		else
1071			list.RemoveItem(index);
1072	}
1073}
1074
1075
1076bool
1077BOutlineListView::_SwapItems(int32 first, int32 second)
1078{
1079	// same item, do nothing
1080	if (first == second)
1081		return true;
1082
1083	// fail, first item out of bounds
1084	if ((first < 0) || (first >= CountItems()))
1085		return false;
1086
1087	// fail, second item out of bounds
1088	if ((second < 0) || (second >= CountItems()))
1089		return false;
1090
1091	int32 firstIndex = min_c(first, second);
1092	int32 secondIndex = max_c(first, second);
1093	BListItem* firstItem = ItemAt(firstIndex);
1094	BListItem* secondItem = ItemAt(secondIndex);
1095	BList firstSubItems, secondSubItems;
1096
1097	if (Superitem(firstItem) != Superitem(secondItem))
1098		return false;
1099
1100	if (!firstItem->IsItemVisible() || !secondItem->IsItemVisible())
1101		return false;
1102
1103	int32 fullFirstIndex = _FullListIndex(firstIndex);
1104	int32 fullSecondIndex = _FullListIndex(secondIndex);
1105	_GetSubItems(fFullList, firstSubItems, firstItem, fullFirstIndex + 1);
1106	_GetSubItems(fFullList, secondSubItems, secondItem, fullSecondIndex + 1);
1107	_DoSwap(fFullList, fullFirstIndex, fullSecondIndex, &firstSubItems,
1108		&secondSubItems);
1109
1110	_CullInvisibleItems(firstSubItems);
1111	_CullInvisibleItems(secondSubItems);
1112	_DoSwap(fList, firstIndex, secondIndex, &firstSubItems,
1113		&secondSubItems);
1114
1115	_RecalcItemTops(firstIndex);
1116	_RescanSelection(firstIndex, secondIndex + secondSubItems.CountItems());
1117	Invalidate(Bounds());
1118
1119	return true;
1120}
1121
1122
1123/*!	\brief Removes a single item from the list and all of its children.
1124
1125	Unlike the BeOS version, this one will actually delete the children, too,
1126	as there should be no reference left to them. This may cause problems for
1127	applications that actually take the misbehaviour of the Be classes into
1128	account.
1129*/
1130BListItem*
1131BOutlineListView::_RemoveItem(BListItem* item, int32 fullListIndex)
1132{
1133	if (item == NULL || fullListIndex < 0
1134		|| fullListIndex >= FullListCountItems()) {
1135		return NULL;
1136	}
1137
1138	uint32 level = item->OutlineLevel();
1139	int32 superIndex;
1140	BListItem* super = _SuperitemForIndex(fullListIndex, level, &superIndex);
1141
1142	if (item->IsItemVisible()) {
1143		// remove children, too
1144		while (fullListIndex + 1 < FullListCountItems()) {
1145			BListItem* subItem = FullListItemAt(fullListIndex + 1);
1146
1147			if (subItem->OutlineLevel() <= level)
1148				break;
1149
1150			if (subItem->IsItemVisible())
1151				BListView::RemoveItem(subItem);
1152
1153			fFullList.RemoveItem(fullListIndex + 1);
1154			delete subItem;
1155		}
1156		BListView::RemoveItem(item);
1157	}
1158
1159	fFullList.RemoveItem(fullListIndex);
1160
1161	if (super != NULL) {
1162		// we might need to change the fHasSubitems field of the parent
1163		BListItem* child = FullListItemAt(superIndex + 1);
1164		if (child == NULL || child->OutlineLevel() <= super->OutlineLevel())
1165			super->fHasSubitems = false;
1166	}
1167
1168	return item;
1169}
1170
1171
1172/*!	Returns the super item before the item specified by \a fullListIndex
1173	and \a level.
1174*/
1175BListItem*
1176BOutlineListView::_SuperitemForIndex(int32 fullListIndex, int32 level,
1177	int32* _superIndex)
1178{
1179	BListItem* item;
1180	fullListIndex--;
1181
1182	while (fullListIndex >= 0) {
1183		if ((item = FullListItemAt(fullListIndex))->OutlineLevel()
1184				< (uint32)level) {
1185			if (_superIndex != NULL)
1186				*_superIndex = fullListIndex;
1187			return item;
1188		}
1189
1190		fullListIndex--;
1191	}
1192
1193	return NULL;
1194}
1195
1196
1197int32
1198BOutlineListView::_FindPreviousVisibleIndex(int32 fullListIndex)
1199{
1200	fullListIndex--;
1201
1202	while (fullListIndex >= 0) {
1203		if (FullListItemAt(fullListIndex)->fVisible)
1204			return fullListIndex;
1205
1206		fullListIndex--;
1207	}
1208
1209	return -1;
1210}
1211
1212
1213status_t
1214BOutlineListView::_ItemsUnderSetup(BListItem* superItem, int32& startIndex, uint32& baseLevel) const
1215{
1216	if (superItem != NULL) {
1217		startIndex = FullListIndexOf(superItem) + 1;
1218		if (startIndex == 0)
1219			return B_ENTRY_NOT_FOUND;
1220		baseLevel = superItem->OutlineLevel() + 1;
1221	} else {
1222		startIndex = 0;
1223		baseLevel = 0;
1224	}
1225	return B_OK;
1226}
1227