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	be_control_look->DrawArrowShape(this, latchRect, itemRect, base,
935		arrowDirection, 0, B_DARKEN_4_TINT);
936}
937
938
939void
940BOutlineListView::DrawItem(BListItem* item, BRect itemRect, bool complete)
941{
942	if (item->fHasSubitems) {
943		DrawLatch(itemRect, item->fLevel, !item->IsExpanded(),
944			item->IsSelected() || complete, false);
945	}
946
947	itemRect.left += LatchRect(itemRect, item->fLevel).right;
948	BListView::DrawItem(item, itemRect, complete);
949}
950
951
952int32
953BOutlineListView::_FullListIndex(int32 index) const
954{
955	BListItem* item = ItemAt(index);
956
957	if (item == NULL)
958		return -1;
959
960	return FullListIndexOf(item);
961}
962
963
964void
965BOutlineListView::_PopulateTree(BList* tree, BList& target,
966	int32& firstIndex, bool onlyVisible)
967{
968	BListItem** items = (BListItem**)target.Items();
969	int32 count = tree->CountItems();
970
971	for (int32 index = 0; index < count; index++) {
972		BListItem* item = (BListItem*)tree->ItemAtFast(index);
973
974		items[firstIndex++] = item;
975
976		if (item->HasSubitems() && (!onlyVisible || item->IsExpanded())) {
977			_PopulateTree(item->fTemporaryList, target, firstIndex,
978				onlyVisible);
979		}
980	}
981}
982
983
984void
985BOutlineListView::_SortTree(BList* tree, bool oneLevelOnly,
986	int (*compareFunc)(const BListItem* a, const BListItem* b))
987{
988	BListItem** items = (BListItem**)tree->Items();
989	std::sort(items, items + tree->CountItems(),
990		ListItemComparator(compareFunc));
991
992	if (oneLevelOnly)
993		return;
994
995	for (int32 index = tree->CountItems(); index-- > 0;) {
996		BListItem* item = (BListItem*)tree->ItemAt(index);
997
998		if (item->HasSubitems())
999			_SortTree(item->fTemporaryList, false, compareFunc);
1000	}
1001}
1002
1003
1004void
1005BOutlineListView::_DestructTree(BList* tree)
1006{
1007	for (int32 index = tree->CountItems(); index-- > 0;) {
1008		BListItem* item = (BListItem*)tree->ItemAt(index);
1009
1010		if (item->HasSubitems())
1011			_DestructTree(item->fTemporaryList);
1012	}
1013
1014	delete tree;
1015}
1016
1017
1018BList*
1019BOutlineListView::_BuildTree(BListItem* superItem, int32& fullListIndex)
1020{
1021	int32 fullCount = FullListCountItems();
1022	uint32 level = superItem != NULL ? superItem->OutlineLevel() + 1 : 0;
1023	BList* list = new BList;
1024	if (superItem != NULL)
1025		superItem->fTemporaryList = list;
1026
1027	while (fullListIndex < fullCount) {
1028		BListItem* item = FullListItemAt(fullListIndex);
1029
1030		// If we jump out of the subtree, break out
1031		if (item->fLevel < level)
1032			break;
1033
1034		// If the level matches, put them into the list
1035		// (we handle the case of a missing sublevel gracefully)
1036		list->AddItem(item);
1037		fullListIndex++;
1038
1039		if (item->HasSubitems()) {
1040			// we're going deeper
1041			_BuildTree(item, fullListIndex);
1042		}
1043	}
1044
1045	return list;
1046}
1047
1048
1049void
1050BOutlineListView::_CullInvisibleItems(BList& list)
1051{
1052	int32 index = 0;
1053	while (index < list.CountItems()) {
1054		if (reinterpret_cast<BListItem*>(list.ItemAt(index))->IsItemVisible())
1055			++index;
1056		else
1057			list.RemoveItem(index);
1058	}
1059}
1060
1061
1062bool
1063BOutlineListView::_SwapItems(int32 first, int32 second)
1064{
1065	// same item, do nothing
1066	if (first == second)
1067		return true;
1068
1069	// fail, first item out of bounds
1070	if ((first < 0) || (first >= CountItems()))
1071		return false;
1072
1073	// fail, second item out of bounds
1074	if ((second < 0) || (second >= CountItems()))
1075		return false;
1076
1077	int32 firstIndex = min_c(first, second);
1078	int32 secondIndex = max_c(first, second);
1079	BListItem* firstItem = ItemAt(firstIndex);
1080	BListItem* secondItem = ItemAt(secondIndex);
1081	BList firstSubItems, secondSubItems;
1082
1083	if (Superitem(firstItem) != Superitem(secondItem))
1084		return false;
1085
1086	if (!firstItem->IsItemVisible() || !secondItem->IsItemVisible())
1087		return false;
1088
1089	int32 fullFirstIndex = _FullListIndex(firstIndex);
1090	int32 fullSecondIndex = _FullListIndex(secondIndex);
1091	_GetSubItems(fFullList, firstSubItems, firstItem, fullFirstIndex + 1);
1092	_GetSubItems(fFullList, secondSubItems, secondItem, fullSecondIndex + 1);
1093	_DoSwap(fFullList, fullFirstIndex, fullSecondIndex, &firstSubItems,
1094		&secondSubItems);
1095
1096	_CullInvisibleItems(firstSubItems);
1097	_CullInvisibleItems(secondSubItems);
1098	_DoSwap(fList, firstIndex, secondIndex, &firstSubItems,
1099		&secondSubItems);
1100
1101	_RecalcItemTops(firstIndex);
1102	_RescanSelection(firstIndex, secondIndex + secondSubItems.CountItems());
1103	Invalidate(Bounds());
1104
1105	return true;
1106}
1107
1108
1109/*!	\brief Removes a single item from the list and all of its children.
1110
1111	Unlike the BeOS version, this one will actually delete the children, too,
1112	as there should be no reference left to them. This may cause problems for
1113	applications that actually take the misbehaviour of the Be classes into
1114	account.
1115*/
1116BListItem*
1117BOutlineListView::_RemoveItem(BListItem* item, int32 fullListIndex)
1118{
1119	if (item == NULL || fullListIndex < 0
1120		|| fullListIndex >= FullListCountItems()) {
1121		return NULL;
1122	}
1123
1124	uint32 level = item->OutlineLevel();
1125	int32 superIndex;
1126	BListItem* super = _SuperitemForIndex(fullListIndex, level, &superIndex);
1127
1128	if (item->IsItemVisible()) {
1129		// remove children, too
1130		while (fullListIndex + 1 < FullListCountItems()) {
1131			BListItem* subItem = FullListItemAt(fullListIndex + 1);
1132
1133			if (subItem->OutlineLevel() <= level)
1134				break;
1135
1136			if (subItem->IsItemVisible())
1137				BListView::RemoveItem(subItem);
1138
1139			fFullList.RemoveItem(fullListIndex + 1);
1140			delete subItem;
1141		}
1142		BListView::RemoveItem(item);
1143	}
1144
1145	fFullList.RemoveItem(fullListIndex);
1146
1147	if (super != NULL) {
1148		// we might need to change the fHasSubitems field of the parent
1149		BListItem* child = FullListItemAt(superIndex + 1);
1150		if (child == NULL || child->OutlineLevel() <= super->OutlineLevel())
1151			super->fHasSubitems = false;
1152	}
1153
1154	return item;
1155}
1156
1157
1158/*!	Returns the super item before the item specified by \a fullListIndex
1159	and \a level.
1160*/
1161BListItem*
1162BOutlineListView::_SuperitemForIndex(int32 fullListIndex, int32 level,
1163	int32* _superIndex)
1164{
1165	BListItem* item;
1166	fullListIndex--;
1167
1168	while (fullListIndex >= 0) {
1169		if ((item = FullListItemAt(fullListIndex))->OutlineLevel()
1170				< (uint32)level) {
1171			if (_superIndex != NULL)
1172				*_superIndex = fullListIndex;
1173			return item;
1174		}
1175
1176		fullListIndex--;
1177	}
1178
1179	return NULL;
1180}
1181
1182
1183int32
1184BOutlineListView::_FindPreviousVisibleIndex(int32 fullListIndex)
1185{
1186	fullListIndex--;
1187
1188	while (fullListIndex >= 0) {
1189		if (FullListItemAt(fullListIndex)->fVisible)
1190			return fullListIndex;
1191
1192		fullListIndex--;
1193	}
1194
1195	return -1;
1196}
1197