xref: /haiku/src/kits/interface/OutlineListView.cpp (revision 68d37cfb3a755a7270d772b505ee15c8b18aa5e0) 
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 
30 typedef int (*compare_func)(const BListItem* a, const BListItem* b);
31 
32 
33 struct 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 
45 private:
46 	compare_func	fCompareFunc;
47 };
48 
49 
50 static 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 
62 static 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 
82 BOutlineListView::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 
90 BOutlineListView::BOutlineListView(const char* name, list_view_type type,
91 	uint32 flags)
92 	:
93 	BListView(name, type, flags)
94 {
95 }
96 
97 
98 BOutlineListView::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 
116 BOutlineListView::~BOutlineListView()
117 {
118 	fFullList.MakeEmpty();
119 }
120 
121 
122 BArchivable*
123 BOutlineListView::Instantiate(BMessage* archive)
124 {
125 	if (validate_instantiation(archive, "BOutlineListView"))
126 		return new BOutlineListView(archive);
127 
128 	return NULL;
129 }
130 
131 
132 status_t
133 BOutlineListView::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 
168 void
169 BOutlineListView::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 
190 void
191 BOutlineListView::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 
233 void
234 BOutlineListView::FrameMoved(BPoint newPosition)
235 {
236 	BListView::FrameMoved(newPosition);
237 }
238 
239 
240 void
241 BOutlineListView::FrameResized(float newWidth, float newHeight)
242 {
243 	BListView::FrameResized(newWidth, newHeight);
244 }
245 
246 
247 void
248 BOutlineListView::MouseUp(BPoint where)
249 {
250 	BListView::MouseUp(where);
251 }
252 
253 
254 bool
255 BOutlineListView::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 
279 bool
280 BOutlineListView::AddItem(BListItem* item)
281 {
282 	return AddItem(item, FullListCountItems());
283 }
284 
285 
286 bool
287 BOutlineListView::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 
331 bool
332 BOutlineListView::AddList(BList* newItems)
333 {
334 	return AddList(newItems, FullListCountItems());
335 }
336 
337 
338 bool
339 BOutlineListView::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 
351 bool
352 BOutlineListView::RemoveItem(BListItem* item)
353 {
354 	return _RemoveItem(item, FullListIndexOf(item)) != NULL;
355 }
356 
357 
358 BListItem*
359 BOutlineListView::RemoveItem(int32 fullListIndex)
360 {
361 	return _RemoveItem(FullListItemAt(fullListIndex), fullListIndex);
362 }
363 
364 
365 bool
366 BOutlineListView::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 
381 BListItem*
382 BOutlineListView::FullListItemAt(int32 fullListIndex) const
383 {
384 	return (BListItem*)fFullList.ItemAt(fullListIndex);
385 }
386 
387 
388 int32
389 BOutlineListView::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 
400 int32
401 BOutlineListView::FullListIndexOf(BListItem* item) const
402 {
403 	return fFullList.IndexOf(item);
404 }
405 
406 
407 BListItem*
408 BOutlineListView::FullListFirstItem() const
409 {
410 	return (BListItem*)fFullList.FirstItem();
411 }
412 
413 
414 BListItem*
415 BOutlineListView::FullListLastItem() const
416 {
417 	return (BListItem*)fFullList.LastItem();
418 }
419 
420 
421 bool
422 BOutlineListView::FullListHasItem(BListItem* item) const
423 {
424 	return fFullList.HasItem(item);
425 }
426 
427 
428 int32
429 BOutlineListView::FullListCountItems() const
430 {
431 	return fFullList.CountItems();
432 }
433 
434 
435 int32
436 BOutlineListView::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 
448 void
449 BOutlineListView::MakeEmpty()
450 {
451 	fFullList.MakeEmpty();
452 	BListView::MakeEmpty();
453 }
454 
455 
456 bool
457 BOutlineListView::FullListIsEmpty() const
458 {
459 	return fFullList.IsEmpty();
460 }
461 
462 
463 void
464 BOutlineListView::FullListDoForEach(bool(*func)(BListItem* item))
465 {
466 	fFullList.DoForEach(reinterpret_cast<bool (*)(void*)>(func));
467 }
468 
469 
470 void
471 BOutlineListView::FullListDoForEach(bool (*func)(BListItem* item, void* arg),
472 	void* arg)
473 {
474 	fFullList.DoForEach(reinterpret_cast<bool (*)(void*, void*)>(func), arg);
475 }
476 
477 
478 BListItem*
479 BOutlineListView::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 
489 void
490 BOutlineListView::Expand(BListItem* item)
491 {
492 	ExpandOrCollapse(item, true);
493 }
494 
495 
496 void
497 BOutlineListView::Collapse(BListItem* item)
498 {
499 	ExpandOrCollapse(item, false);
500 }
501 
502 
503 bool
504 BOutlineListView::IsExpanded(int32 fullListIndex)
505 {
506 	BListItem* item = FullListItemAt(fullListIndex);
507 	if (!item)
508 		return false;
509 
510 	return item->IsExpanded();
511 }
512 
513 
514 BHandler*
515 BOutlineListView::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 
523 status_t
524 BOutlineListView::GetSupportedSuites(BMessage* data)
525 {
526 	return BListView::GetSupportedSuites(data);
527 }
528 
529 
530 status_t
531 BOutlineListView::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 
586 void
587 BOutlineListView::ResizeToPreferred()
588 {
589 	BListView::ResizeToPreferred();
590 }
591 
592 
593 void
594 BOutlineListView::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 
619 void
620 BOutlineListView::MakeFocus(bool state)
621 {
622 	BListView::MakeFocus(state);
623 }
624 
625 
626 void
627 BOutlineListView::AllAttached()
628 {
629 	BListView::AllAttached();
630 }
631 
632 
633 void
634 BOutlineListView::AllDetached()
635 {
636 	BListView::AllDetached();
637 }
638 
639 
640 void
641 BOutlineListView::DetachedFromWindow()
642 {
643 	BListView::DetachedFromWindow();
644 }
645 
646 
647 void
648 BOutlineListView::FullListSortItems(int (*compareFunc)(const BListItem* a,
649 	const BListItem* b))
650 {
651 	SortItemsUnder(NULL, false, compareFunc);
652 }
653 
654 
655 void
656 BOutlineListView::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 
697 int32
698 BOutlineListView::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 
724 BListItem*
725 BOutlineListView::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 
754 BListItem*
755 BOutlineListView::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 
784 bool
785 BOutlineListView::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 
794 void
795 BOutlineListView::MessageReceived(BMessage* msg)
796 {
797 	BListView::MessageReceived(msg);
798 }
799 
800 
801 void BOutlineListView::_ReservedOutlineListView1() {}
802 void BOutlineListView::_ReservedOutlineListView2() {}
803 void BOutlineListView::_ReservedOutlineListView3() {}
804 void BOutlineListView::_ReservedOutlineListView4() {}
805 
806 
807 void
808 BOutlineListView::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 
915 BRect
916 BOutlineListView::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 
929 void
930 BOutlineListView::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 
948 void
949 BOutlineListView::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 
961 int32
962 BOutlineListView::_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 
973 void
974 BOutlineListView::_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 
993 void
994 BOutlineListView::_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 
1013 void
1014 BOutlineListView::_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 
1027 BList*
1028 BOutlineListView::_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 
1058 void
1059 BOutlineListView::_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 
1071 bool
1072 BOutlineListView::_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 */
1125 BListItem*
1126 BOutlineListView::_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 */
1170 BListItem*
1171 BOutlineListView::_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 
1192 int32
1193 BOutlineListView::_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