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 = FullListIndexOf(superItem);
701	if (i == -1)
702		return 0;
703
704	++i;
705	int32 count = 0;
706	uint32 baseLevel = superItem->OutlineLevel();
707
708	for (; i < FullListCountItems(); i++) {
709		BListItem* item = FullListItemAt(i);
710
711		// If we jump out of the subtree, return count
712		if (item->fLevel <= baseLevel)
713			return count;
714
715		// If the level matches, increase count
716		if (!oneLevelOnly || item->fLevel == baseLevel + 1)
717			count++;
718	}
719
720	return count;
721}
722
723
724BListItem*
725BOutlineListView::EachItemUnder(BListItem* superItem, bool oneLevelOnly,
726	BListItem* (*eachFunc)(BListItem* item, void* arg), void* arg)
727{
728	int32 i = FullListIndexOf(superItem);
729	if (i == -1)
730		return NULL;
731
732	i++; // skip the superitem
733	while (i < FullListCountItems()) {
734		BListItem* item = FullListItemAt(i);
735
736		// If we jump out of the subtree, return NULL
737		if (item->fLevel <= superItem->OutlineLevel())
738			return NULL;
739
740		// If the level matches, check the index
741		if (!oneLevelOnly || item->fLevel == superItem->OutlineLevel() + 1) {
742			item = eachFunc(item, arg);
743			if (item != NULL)
744				return item;
745		}
746
747		i++;
748	}
749
750	return NULL;
751}
752
753
754BListItem*
755BOutlineListView::ItemUnderAt(BListItem* superItem, bool oneLevelOnly,
756	int32 index) const
757{
758	int32 i = FullListIndexOf(superItem);
759	if (i == -1)
760		return NULL;
761
762	while (i < FullListCountItems()) {
763		BListItem* item = FullListItemAt(i);
764
765		// If we jump out of the subtree, return NULL
766		if (item->fLevel < superItem->OutlineLevel())
767			return NULL;
768
769		// If the level matches, check the index
770		if (!oneLevelOnly || item->fLevel == superItem->OutlineLevel() + 1) {
771			if (index == 0)
772				return item;
773
774			index--;
775		}
776
777		i++;
778	}
779
780	return NULL;
781}
782
783
784bool
785BOutlineListView::DoMiscellaneous(MiscCode code, MiscData* data)
786{
787	if (code == B_SWAP_OP)
788		return _SwapItems(data->swap.a, data->swap.b);
789
790	return BListView::DoMiscellaneous(code, data);
791}
792
793
794void
795BOutlineListView::MessageReceived(BMessage* msg)
796{
797	BListView::MessageReceived(msg);
798}
799
800
801void BOutlineListView::_ReservedOutlineListView1() {}
802void BOutlineListView::_ReservedOutlineListView2() {}
803void BOutlineListView::_ReservedOutlineListView3() {}
804void BOutlineListView::_ReservedOutlineListView4() {}
805
806
807void
808BOutlineListView::ExpandOrCollapse(BListItem* item, bool expand)
809{
810	if (item->IsExpanded() == expand || !FullListHasItem(item))
811		return;
812
813	item->fExpanded = expand;
814
815	// TODO: merge these cases together, they are pretty similar
816
817	if (expand) {
818		uint32 level = item->fLevel;
819		int32 fullListIndex = FullListIndexOf(item);
820		int32 index = IndexOf(item) + 1;
821		int32 startIndex = index;
822		int32 count = FullListCountItems() - fullListIndex - 1;
823		BListItem** items = (BListItem**)fFullList.Items() + fullListIndex + 1;
824
825		BFont font;
826		GetFont(&font);
827		while (count-- > 0) {
828			item = items[0];
829			if (item->fLevel <= level)
830				break;
831
832			if (!item->IsItemVisible()) {
833				// fix selection hints
834				if (index <= fFirstSelected)
835					fFirstSelected++;
836				if (index <= fLastSelected)
837					fLastSelected++;
838
839				fList.AddItem(item, index++);
840				item->Update(this, &font);
841				item->SetItemVisible(true);
842			}
843
844			if (item->HasSubitems() && !item->IsExpanded()) {
845				// Skip hidden children
846				uint32 subLevel = item->fLevel;
847				items++;
848
849				while (--count > 0 && items[0]->fLevel > subLevel)
850					items++;
851			} else
852				items++;
853		}
854		_RecalcItemTops(startIndex);
855	} else {
856		// collapse
857		uint32 level = item->fLevel;
858		int32 fullListIndex = FullListIndexOf(item);
859		int32 index = IndexOf(item);
860		int32 startIndex = index;
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(startIndex);
886		// fix selection hints
887		// if the selected item was just removed by collapsing, select its
888		// parent
889		if (ListType() == B_SINGLE_SELECTION_LIST && selectionChanged)
890			fFirstSelected = fLastSelected = index;
891
892		if (index < fFirstSelected && index + count < fFirstSelected) {
893				// all items removed were higher than the selection range,
894				// adjust the indexes to correspond to their new visible positions
895				fFirstSelected -= count;
896				fLastSelected -= count;
897		}
898
899		int32 maxIndex = fList.CountItems() - 1;
900		if (fFirstSelected > maxIndex)
901			fFirstSelected = maxIndex;
902
903		if (fLastSelected > maxIndex)
904			fLastSelected = maxIndex;
905
906		if (selectionChanged)
907			SelectionChanged();
908	}
909
910	_FixupScrollBar();
911	Invalidate();
912}
913
914
915BRect
916BOutlineListView::LatchRect(BRect itemRect, int32 level) const
917{
918	float latchWidth = be_plain_font->Size();
919	float latchHeight = be_plain_font->Size();
920	float indentOffset = level * be_control_look->DefaultItemSpacing();
921	float heightOffset = itemRect.Height() / 2 - latchHeight / 2;
922
923	return BRect(0, 0, latchWidth, latchHeight)
924		.OffsetBySelf(itemRect.left, itemRect.top)
925		.OffsetBySelf(indentOffset, heightOffset);
926}
927
928
929void
930BOutlineListView::DrawLatch(BRect itemRect, int32 level, bool collapsed,
931	bool highlighted, bool misTracked)
932{
933	BRect latchRect(LatchRect(itemRect, level));
934	rgb_color base = ui_color(B_PANEL_BACKGROUND_COLOR);
935	int32 arrowDirection = collapsed ? BControlLook::B_RIGHT_ARROW
936		: BControlLook::B_DOWN_ARROW;
937
938	float tintColor = B_DARKEN_4_TINT;
939	if (base.red + base.green + base.blue <= 128 * 3) {
940		tintColor = B_LIGHTEN_2_TINT;
941	}
942
943	be_control_look->DrawArrowShape(this, latchRect, itemRect, base,
944		arrowDirection, 0, tintColor);
945}
946
947
948void
949BOutlineListView::DrawItem(BListItem* item, BRect itemRect, bool complete)
950{
951	if (item->fHasSubitems) {
952		DrawLatch(itemRect, item->fLevel, !item->IsExpanded(),
953			item->IsSelected() || complete, false);
954	}
955
956	itemRect.left += LatchRect(itemRect, item->fLevel).right;
957	BListView::DrawItem(item, itemRect, complete);
958}
959
960
961int32
962BOutlineListView::_FullListIndex(int32 index) const
963{
964	BListItem* item = ItemAt(index);
965
966	if (item == NULL)
967		return -1;
968
969	return FullListIndexOf(item);
970}
971
972
973void
974BOutlineListView::_PopulateTree(BList* tree, BList& target,
975	int32& firstIndex, bool onlyVisible)
976{
977	BListItem** items = (BListItem**)target.Items();
978	int32 count = tree->CountItems();
979
980	for (int32 index = 0; index < count; index++) {
981		BListItem* item = (BListItem*)tree->ItemAtFast(index);
982
983		items[firstIndex++] = item;
984
985		if (item->HasSubitems() && (!onlyVisible || item->IsExpanded())) {
986			_PopulateTree(item->fTemporaryList, target, firstIndex,
987				onlyVisible);
988		}
989	}
990}
991
992
993void
994BOutlineListView::_SortTree(BList* tree, bool oneLevelOnly,
995	int (*compareFunc)(const BListItem* a, const BListItem* b))
996{
997	BListItem** items = (BListItem**)tree->Items();
998	std::sort(items, items + tree->CountItems(),
999		ListItemComparator(compareFunc));
1000
1001	if (oneLevelOnly)
1002		return;
1003
1004	for (int32 index = tree->CountItems(); index-- > 0;) {
1005		BListItem* item = (BListItem*)tree->ItemAt(index);
1006
1007		if (item->HasSubitems())
1008			_SortTree(item->fTemporaryList, false, compareFunc);
1009	}
1010}
1011
1012
1013void
1014BOutlineListView::_DestructTree(BList* tree)
1015{
1016	for (int32 index = tree->CountItems(); index-- > 0;) {
1017		BListItem* item = (BListItem*)tree->ItemAt(index);
1018
1019		if (item->HasSubitems())
1020			_DestructTree(item->fTemporaryList);
1021	}
1022
1023	delete tree;
1024}
1025
1026
1027BList*
1028BOutlineListView::_BuildTree(BListItem* superItem, int32& fullListIndex)
1029{
1030	int32 fullCount = FullListCountItems();
1031	uint32 level = superItem != NULL ? superItem->OutlineLevel() + 1 : 0;
1032	BList* list = new BList;
1033	if (superItem != NULL)
1034		superItem->fTemporaryList = list;
1035
1036	while (fullListIndex < fullCount) {
1037		BListItem* item = FullListItemAt(fullListIndex);
1038
1039		// If we jump out of the subtree, break out
1040		if (item->fLevel < level)
1041			break;
1042
1043		// If the level matches, put them into the list
1044		// (we handle the case of a missing sublevel gracefully)
1045		list->AddItem(item);
1046		fullListIndex++;
1047
1048		if (item->HasSubitems()) {
1049			// we're going deeper
1050			_BuildTree(item, fullListIndex);
1051		}
1052	}
1053
1054	return list;
1055}
1056
1057
1058void
1059BOutlineListView::_CullInvisibleItems(BList& list)
1060{
1061	int32 index = 0;
1062	while (index < list.CountItems()) {
1063		if (reinterpret_cast<BListItem*>(list.ItemAt(index))->IsItemVisible())
1064			++index;
1065		else
1066			list.RemoveItem(index);
1067	}
1068}
1069
1070
1071bool
1072BOutlineListView::_SwapItems(int32 first, int32 second)
1073{
1074	// same item, do nothing
1075	if (first == second)
1076		return true;
1077
1078	// fail, first item out of bounds
1079	if ((first < 0) || (first >= CountItems()))
1080		return false;
1081
1082	// fail, second item out of bounds
1083	if ((second < 0) || (second >= CountItems()))
1084		return false;
1085
1086	int32 firstIndex = min_c(first, second);
1087	int32 secondIndex = max_c(first, second);
1088	BListItem* firstItem = ItemAt(firstIndex);
1089	BListItem* secondItem = ItemAt(secondIndex);
1090	BList firstSubItems, secondSubItems;
1091
1092	if (Superitem(firstItem) != Superitem(secondItem))
1093		return false;
1094
1095	if (!firstItem->IsItemVisible() || !secondItem->IsItemVisible())
1096		return false;
1097
1098	int32 fullFirstIndex = _FullListIndex(firstIndex);
1099	int32 fullSecondIndex = _FullListIndex(secondIndex);
1100	_GetSubItems(fFullList, firstSubItems, firstItem, fullFirstIndex + 1);
1101	_GetSubItems(fFullList, secondSubItems, secondItem, fullSecondIndex + 1);
1102	_DoSwap(fFullList, fullFirstIndex, fullSecondIndex, &firstSubItems,
1103		&secondSubItems);
1104
1105	_CullInvisibleItems(firstSubItems);
1106	_CullInvisibleItems(secondSubItems);
1107	_DoSwap(fList, firstIndex, secondIndex, &firstSubItems,
1108		&secondSubItems);
1109
1110	_RecalcItemTops(firstIndex);
1111	_RescanSelection(firstIndex, secondIndex + secondSubItems.CountItems());
1112	Invalidate(Bounds());
1113
1114	return true;
1115}
1116
1117
1118/*!	\brief Removes a single item from the list and all of its children.
1119
1120	Unlike the BeOS version, this one will actually delete the children, too,
1121	as there should be no reference left to them. This may cause problems for
1122	applications that actually take the misbehaviour of the Be classes into
1123	account.
1124*/
1125BListItem*
1126BOutlineListView::_RemoveItem(BListItem* item, int32 fullListIndex)
1127{
1128	if (item == NULL || fullListIndex < 0
1129		|| fullListIndex >= FullListCountItems()) {
1130		return NULL;
1131	}
1132
1133	uint32 level = item->OutlineLevel();
1134	int32 superIndex;
1135	BListItem* super = _SuperitemForIndex(fullListIndex, level, &superIndex);
1136
1137	if (item->IsItemVisible()) {
1138		// remove children, too
1139		while (fullListIndex + 1 < FullListCountItems()) {
1140			BListItem* subItem = FullListItemAt(fullListIndex + 1);
1141
1142			if (subItem->OutlineLevel() <= level)
1143				break;
1144
1145			if (subItem->IsItemVisible())
1146				BListView::RemoveItem(subItem);
1147
1148			fFullList.RemoveItem(fullListIndex + 1);
1149			delete subItem;
1150		}
1151		BListView::RemoveItem(item);
1152	}
1153
1154	fFullList.RemoveItem(fullListIndex);
1155
1156	if (super != NULL) {
1157		// we might need to change the fHasSubitems field of the parent
1158		BListItem* child = FullListItemAt(superIndex + 1);
1159		if (child == NULL || child->OutlineLevel() <= super->OutlineLevel())
1160			super->fHasSubitems = false;
1161	}
1162
1163	return item;
1164}
1165
1166
1167/*!	Returns the super item before the item specified by \a fullListIndex
1168	and \a level.
1169*/
1170BListItem*
1171BOutlineListView::_SuperitemForIndex(int32 fullListIndex, int32 level,
1172	int32* _superIndex)
1173{
1174	BListItem* item;
1175	fullListIndex--;
1176
1177	while (fullListIndex >= 0) {
1178		if ((item = FullListItemAt(fullListIndex))->OutlineLevel()
1179				< (uint32)level) {
1180			if (_superIndex != NULL)
1181				*_superIndex = fullListIndex;
1182			return item;
1183		}
1184
1185		fullListIndex--;
1186	}
1187
1188	return NULL;
1189}
1190
1191
1192int32
1193BOutlineListView::_FindPreviousVisibleIndex(int32 fullListIndex)
1194{
1195	fullListIndex--;
1196
1197	while (fullListIndex >= 0) {
1198		if (FullListItemAt(fullListIndex)->fVisible)
1199			return fullListIndex;
1200
1201		fullListIndex--;
1202	}
1203
1204	return -1;
1205}
1206