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