xref: /haiku/src/kits/interface/OutlineListView.cpp (revision 445d4fd926c569e7b9ae28017da86280aaecbae2) 
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 					count--;
852 				}
853 			} else
854 				items++;
855 		}
856 		_RecalcItemTops(startIndex);
857 	} else {
858 		// collapse
859 		const uint32 level = item->fLevel;
860 		const int32 fullListIndex = FullListIndexOf(item);
861 		const int32 index = IndexOf(item);
862 		int32 max = FullListCountItems() - fullListIndex - 1;
863 		int32 count = 0;
864 		bool selectionChanged = false;
865 
866 		BListItem** items = (BListItem**)fFullList.Items() + fullListIndex + 1;
867 
868 		while (max-- > 0) {
869 			item = items[0];
870 			if (item->fLevel <= level)
871 				break;
872 
873 			if (item->IsItemVisible()) {
874 				fList.RemoveItem(item);
875 				item->SetItemVisible(false);
876 				if (item->IsSelected()) {
877 					selectionChanged = true;
878 					item->Deselect();
879 				}
880 				count++;
881 			}
882 
883 			items++;
884 		}
885 
886 		_RecalcItemTops(index);
887 		// fix selection hints
888 		// if the selected item was just removed by collapsing, select its
889 		// parent
890 		if (selectionChanged) {
891 			if (fFirstSelected > index && fFirstSelected <= index + count) {
892 					fFirstSelected = index;
893 			}
894 			if (fLastSelected > index && fLastSelected <= index + count) {
895 				fLastSelected = index;
896 			}
897 		}
898 		if (index + count < fFirstSelected) {
899 				// all items removed were higher than the selection range,
900 				// adjust the indexes to correspond to their new visible positions
901 				fFirstSelected -= count;
902 				fLastSelected -= count;
903 		}
904 
905 		int32 maxIndex = fList.CountItems() - 1;
906 		if (fFirstSelected > maxIndex)
907 			fFirstSelected = maxIndex;
908 
909 		if (fLastSelected > maxIndex)
910 			fLastSelected = maxIndex;
911 
912 		if (selectionChanged)
913 			Select(fFirstSelected, fLastSelected);
914 	}
915 
916 	_FixupScrollBar();
917 	Invalidate();
918 }
919 
920 
921 BRect
922 BOutlineListView::LatchRect(BRect itemRect, int32 level) const
923 {
924 	float latchWidth = be_plain_font->Size();
925 	float latchHeight = be_plain_font->Size();
926 	float indentOffset = level * be_control_look->DefaultItemSpacing();
927 	float heightOffset = itemRect.Height() / 2 - latchHeight / 2;
928 
929 	return BRect(0, 0, latchWidth, latchHeight)
930 		.OffsetBySelf(itemRect.left, itemRect.top)
931 		.OffsetBySelf(indentOffset, heightOffset);
932 }
933 
934 
935 void
936 BOutlineListView::DrawLatch(BRect itemRect, int32 level, bool collapsed,
937 	bool highlighted, bool misTracked)
938 {
939 	BRect latchRect(LatchRect(itemRect, level));
940 	rgb_color base = ui_color(B_PANEL_BACKGROUND_COLOR);
941 	int32 arrowDirection = collapsed ? BControlLook::B_RIGHT_ARROW
942 		: BControlLook::B_DOWN_ARROW;
943 
944 	float tintColor = B_DARKEN_4_TINT;
945 	if (base.red + base.green + base.blue <= 128 * 3) {
946 		tintColor = B_LIGHTEN_2_TINT;
947 	}
948 
949 	be_control_look->DrawArrowShape(this, latchRect, itemRect, base,
950 		arrowDirection, 0, tintColor);
951 }
952 
953 
954 void
955 BOutlineListView::DrawItem(BListItem* item, BRect itemRect, bool complete)
956 {
957 	if (item->fHasSubitems) {
958 		DrawLatch(itemRect, item->fLevel, !item->IsExpanded(),
959 			item->IsSelected() || complete, false);
960 	}
961 
962 	itemRect.left += LatchRect(itemRect, item->fLevel).right;
963 	BListView::DrawItem(item, itemRect, complete);
964 }
965 
966 
967 int32
968 BOutlineListView::_FullListIndex(int32 index) const
969 {
970 	BListItem* item = ItemAt(index);
971 
972 	if (item == NULL)
973 		return -1;
974 
975 	return FullListIndexOf(item);
976 }
977 
978 
979 void
980 BOutlineListView::_PopulateTree(BList* tree, BList& target,
981 	int32& firstIndex, bool onlyVisible)
982 {
983 	BListItem** items = (BListItem**)target.Items();
984 	int32 count = tree->CountItems();
985 
986 	for (int32 index = 0; index < count; index++) {
987 		BListItem* item = (BListItem*)tree->ItemAtFast(index);
988 
989 		items[firstIndex++] = item;
990 
991 		if (item->HasSubitems() && (!onlyVisible || item->IsExpanded())) {
992 			_PopulateTree(item->fTemporaryList, target, firstIndex,
993 				onlyVisible);
994 		}
995 	}
996 }
997 
998 
999 void
1000 BOutlineListView::_SortTree(BList* tree, bool oneLevelOnly,
1001 	int (*compareFunc)(const BListItem* a, const BListItem* b))
1002 {
1003 	BListItem** items = (BListItem**)tree->Items();
1004 	std::sort(items, items + tree->CountItems(),
1005 		ListItemComparator(compareFunc));
1006 
1007 	if (oneLevelOnly)
1008 		return;
1009 
1010 	for (int32 index = tree->CountItems(); index-- > 0;) {
1011 		BListItem* item = (BListItem*)tree->ItemAt(index);
1012 
1013 		if (item->HasSubitems())
1014 			_SortTree(item->fTemporaryList, false, compareFunc);
1015 	}
1016 }
1017 
1018 
1019 void
1020 BOutlineListView::_DestructTree(BList* tree)
1021 {
1022 	for (int32 index = tree->CountItems(); index-- > 0;) {
1023 		BListItem* item = (BListItem*)tree->ItemAt(index);
1024 
1025 		if (item->HasSubitems())
1026 			_DestructTree(item->fTemporaryList);
1027 	}
1028 
1029 	delete tree;
1030 }
1031 
1032 
1033 BList*
1034 BOutlineListView::_BuildTree(BListItem* superItem, int32& fullListIndex)
1035 {
1036 	int32 fullCount = FullListCountItems();
1037 	uint32 level = superItem != NULL ? superItem->OutlineLevel() + 1 : 0;
1038 	BList* list = new BList;
1039 	if (superItem != NULL)
1040 		superItem->fTemporaryList = list;
1041 
1042 	while (fullListIndex < fullCount) {
1043 		BListItem* item = FullListItemAt(fullListIndex);
1044 
1045 		// If we jump out of the subtree, break out
1046 		if (item->fLevel < level)
1047 			break;
1048 
1049 		// If the level matches, put them into the list
1050 		// (we handle the case of a missing sublevel gracefully)
1051 		list->AddItem(item);
1052 		fullListIndex++;
1053 
1054 		if (item->HasSubitems()) {
1055 			// we're going deeper
1056 			_BuildTree(item, fullListIndex);
1057 		}
1058 	}
1059 
1060 	return list;
1061 }
1062 
1063 
1064 void
1065 BOutlineListView::_CullInvisibleItems(BList& list)
1066 {
1067 	int32 index = 0;
1068 	while (index < list.CountItems()) {
1069 		if (reinterpret_cast<BListItem*>(list.ItemAt(index))->IsItemVisible())
1070 			++index;
1071 		else
1072 			list.RemoveItem(index);
1073 	}
1074 }
1075 
1076 
1077 bool
1078 BOutlineListView::_SwapItems(int32 first, int32 second)
1079 {
1080 	// same item, do nothing
1081 	if (first == second)
1082 		return true;
1083 
1084 	// fail, first item out of bounds
1085 	if ((first < 0) || (first >= CountItems()))
1086 		return false;
1087 
1088 	// fail, second item out of bounds
1089 	if ((second < 0) || (second >= CountItems()))
1090 		return false;
1091 
1092 	int32 firstIndex = min_c(first, second);
1093 	int32 secondIndex = max_c(first, second);
1094 	BListItem* firstItem = ItemAt(firstIndex);
1095 	BListItem* secondItem = ItemAt(secondIndex);
1096 	BList firstSubItems, secondSubItems;
1097 
1098 	if (Superitem(firstItem) != Superitem(secondItem))
1099 		return false;
1100 
1101 	if (!firstItem->IsItemVisible() || !secondItem->IsItemVisible())
1102 		return false;
1103 
1104 	int32 fullFirstIndex = _FullListIndex(firstIndex);
1105 	int32 fullSecondIndex = _FullListIndex(secondIndex);
1106 	_GetSubItems(fFullList, firstSubItems, firstItem, fullFirstIndex + 1);
1107 	_GetSubItems(fFullList, secondSubItems, secondItem, fullSecondIndex + 1);
1108 	_DoSwap(fFullList, fullFirstIndex, fullSecondIndex, &firstSubItems,
1109 		&secondSubItems);
1110 
1111 	_CullInvisibleItems(firstSubItems);
1112 	_CullInvisibleItems(secondSubItems);
1113 	_DoSwap(fList, firstIndex, secondIndex, &firstSubItems,
1114 		&secondSubItems);
1115 
1116 	_RecalcItemTops(firstIndex);
1117 	_RescanSelection(firstIndex, secondIndex + secondSubItems.CountItems());
1118 	Invalidate(Bounds());
1119 
1120 	return true;
1121 }
1122 
1123 
1124 /*!	\brief Removes a single item from the list and all of its children.
1125 
1126 	Unlike the BeOS version, this one will actually delete the children, too,
1127 	as there should be no reference left to them. This may cause problems for
1128 	applications that actually take the misbehaviour of the Be classes into
1129 	account.
1130 */
1131 BListItem*
1132 BOutlineListView::_RemoveItem(BListItem* item, int32 fullListIndex)
1133 {
1134 	if (item == NULL || fullListIndex < 0
1135 		|| fullListIndex >= FullListCountItems()) {
1136 		return NULL;
1137 	}
1138 
1139 	uint32 level = item->OutlineLevel();
1140 	int32 superIndex;
1141 	BListItem* super = _SuperitemForIndex(fullListIndex, level, &superIndex);
1142 
1143 	if (item->IsItemVisible()) {
1144 		// remove children, too
1145 		while (fullListIndex + 1 < FullListCountItems()) {
1146 			BListItem* subItem = FullListItemAt(fullListIndex + 1);
1147 
1148 			if (subItem->OutlineLevel() <= level)
1149 				break;
1150 
1151 			if (subItem->IsItemVisible())
1152 				BListView::RemoveItem(subItem);
1153 
1154 			fFullList.RemoveItem(fullListIndex + 1);
1155 			delete subItem;
1156 		}
1157 		BListView::RemoveItem(item);
1158 	}
1159 
1160 	fFullList.RemoveItem(fullListIndex);
1161 
1162 	if (super != NULL) {
1163 		// we might need to change the fHasSubitems field of the parent
1164 		BListItem* child = FullListItemAt(superIndex + 1);
1165 		if (child == NULL || child->OutlineLevel() <= super->OutlineLevel())
1166 			super->fHasSubitems = false;
1167 	}
1168 
1169 	return item;
1170 }
1171 
1172 
1173 /*!	Returns the super item before the item specified by \a fullListIndex
1174 	and \a level.
1175 */
1176 BListItem*
1177 BOutlineListView::_SuperitemForIndex(int32 fullListIndex, int32 level,
1178 	int32* _superIndex)
1179 {
1180 	BListItem* item;
1181 	fullListIndex--;
1182 
1183 	while (fullListIndex >= 0) {
1184 		if ((item = FullListItemAt(fullListIndex))->OutlineLevel()
1185 				< (uint32)level) {
1186 			if (_superIndex != NULL)
1187 				*_superIndex = fullListIndex;
1188 			return item;
1189 		}
1190 
1191 		fullListIndex--;
1192 	}
1193 
1194 	return NULL;
1195 }
1196 
1197 
1198 int32
1199 BOutlineListView::_FindPreviousVisibleIndex(int32 fullListIndex)
1200 {
1201 	fullListIndex--;
1202 
1203 	while (fullListIndex >= 0) {
1204 		if (FullListItemAt(fullListIndex)->fVisible)
1205 			return fullListIndex;
1206 
1207 		fullListIndex--;
1208 	}
1209 
1210 	return -1;
1211 }
1212