xref: /haiku/src/kits/interface/OutlineListView.cpp (revision c19cb4ddc6456b53da867b06395c58d7dc1efa77) 
1 /*
2  * Copyright 2001-2013 Haiku, Inc.
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 //! BOutlineListView represents a "nestable" list view.
14 
15 #include <OutlineListView.h>
16 
17 #include <algorithm>
18 
19 #include <stdio.h>
20 #include <stdlib.h>
21 
22 #include <ControlLook.h>
23 #include <Window.h>
24 
25 #include <binary_compatibility/Interface.h>
26 
27 
28 typedef int (*compare_func)(const BListItem* a, const BListItem* b);
29 
30 struct ListItemComparator {
31 	ListItemComparator(compare_func compareFunc)
32 		:
33 		fCompareFunc(compareFunc)
34 	{
35 	}
36 
37 	bool operator()(const BListItem* a, const BListItem* b) const
38 	{
39 		return fCompareFunc(a, b) < 0;
40 	}
41 
42 private:
43 	compare_func	fCompareFunc;
44 };
45 
46 
47 static void
48 _GetSubItems(BList& sourceList, BList& destList, BListItem* parent, int32 start)
49 {
50 	for (int32 i = start; i < sourceList.CountItems(); i++) {
51 		BListItem* item = (BListItem*)sourceList.ItemAt(i);
52 		if (item->OutlineLevel() <= parent->OutlineLevel())
53 			break;
54 		destList.AddItem(item);
55 	}
56 }
57 
58 
59 static void
60 _DoSwap(BList& list, int32 firstIndex, int32 secondIndex, BList* firstItems,
61 	BList* secondItems)
62 {
63 	BListItem* item = (BListItem*)list.ItemAt(firstIndex);
64 	list.SwapItems(firstIndex, secondIndex);
65 	list.RemoveItems(secondIndex + 1, secondItems->CountItems());
66 	list.RemoveItems(firstIndex + 1, firstItems->CountItems());
67 	list.AddList(secondItems, firstIndex + 1);
68 	int32 newIndex = list.IndexOf(item);
69 	if (newIndex + 1 < list.CountItems())
70 		list.AddList(firstItems, newIndex + 1);
71 	else
72 		list.AddList(firstItems);
73 }
74 
75 
76 //	#pragma mark -
77 
78 
79 BOutlineListView::BOutlineListView(BRect frame, const char* name,
80 		list_view_type type, uint32 resizeMode, uint32 flags)
81 	: BListView(frame, name, type, resizeMode, flags)
82 {
83 }
84 
85 
86 BOutlineListView::BOutlineListView(const char* name, list_view_type type,
87 		uint32 flags)
88 	: BListView(name, type, flags)
89 {
90 }
91 
92 
93 BOutlineListView::BOutlineListView(BMessage* archive)
94 	: BListView(archive)
95 {
96 	int32 i = 0;
97 	BMessage subData;
98 	while (archive->FindMessage("_l_full_items", i++, &subData) == B_OK) {
99 		BArchivable* object = instantiate_object(&subData);
100 		if (!object)
101 			continue;
102 
103 		BListItem* item = dynamic_cast<BListItem*>(object);
104 		if (item)
105 			AddItem(item);
106 	}
107 }
108 
109 
110 BOutlineListView::~BOutlineListView()
111 {
112 	fFullList.MakeEmpty();
113 }
114 
115 
116 BArchivable*
117 BOutlineListView::Instantiate(BMessage* archive)
118 {
119 	if (validate_instantiation(archive, "BOutlineListView"))
120 		return new BOutlineListView(archive);
121 
122 	return NULL;
123 }
124 
125 
126 status_t
127 BOutlineListView::Archive(BMessage* archive, bool deep) const
128 {
129 	// Note: We can't call the BListView Archive function here, as we are also
130 	// interested in subitems BOutlineListView can have. They are even stored
131 	// with a different field name (_l_full_items vs. _l_items).
132 
133 	status_t status = BView::Archive(archive, deep);
134 	if (status != B_OK)
135 		return status;
136 
137 	status = archive->AddInt32("_lv_type", fListType);
138 	if (status == B_OK && deep) {
139 		int32 i = 0;
140 		BListItem* item = NULL;
141 		while ((item = static_cast<BListItem*>(fFullList.ItemAt(i++)))) {
142 			BMessage subData;
143 			status = item->Archive(&subData, true);
144 			if (status >= B_OK)
145 				status = archive->AddMessage("_l_full_items", &subData);
146 
147 			if (status < B_OK)
148 				break;
149 		}
150 	}
151 
152 	if (status >= B_OK && InvocationMessage() != NULL)
153 		status = archive->AddMessage("_msg", InvocationMessage());
154 
155 	if (status == B_OK && fSelectMessage != NULL)
156 		status = archive->AddMessage("_2nd_msg", fSelectMessage);
157 
158 	return status;
159 }
160 
161 
162 void
163 BOutlineListView::MouseDown(BPoint point)
164 {
165 	MakeFocus();
166 
167 	int32 index = IndexOf(point);
168 
169 	if (index != -1) {
170 		BListItem* item = ItemAt(index);
171 
172 		if (item->fHasSubitems
173 			&& LatchRect(ItemFrame(index), item->fLevel).Contains(point)) {
174 			if (item->IsExpanded())
175 				Collapse(item);
176 			else
177 				Expand(item);
178 		} else
179 			BListView::MouseDown(point);
180 	}
181 }
182 
183 
184 void
185 BOutlineListView::KeyDown(const char* bytes, int32 numBytes)
186 {
187 	if (numBytes == 1) {
188 		int32 currentSel = CurrentSelection();
189 		switch (bytes[0]) {
190 			case B_RIGHT_ARROW:
191 			{
192 				BListItem* item = ItemAt(currentSel);
193 				if (item && item->fHasSubitems) {
194 					if (!IsExpanded(currentSel))
195 						Expand(item);
196 					else
197 						Select(currentSel + 1);
198 				}
199 				return;
200 			}
201 
202 			case B_LEFT_ARROW:
203 			{
204 				BListItem* item = ItemAt(currentSel);
205 				if (item) {
206 					if (item->fHasSubitems)
207 						Collapse(item);
208 					else {
209 						item = Superitem(item);
210 						if (item)
211 							Select(IndexOf(item));
212 					}
213 				}
214 				return;
215 			}
216 		}
217 	}
218 
219 	BListView::KeyDown(bytes, numBytes);
220 }
221 
222 
223 void
224 BOutlineListView::FrameMoved(BPoint newPosition)
225 {
226 	BListView::FrameMoved(newPosition);
227 }
228 
229 
230 void
231 BOutlineListView::FrameResized(float newWidth, float newHeight)
232 {
233 	BListView::FrameResized(newWidth, newHeight);
234 }
235 
236 
237 void
238 BOutlineListView::MouseUp(BPoint where)
239 {
240 	BListView::MouseUp(where);
241 }
242 
243 
244 bool
245 BOutlineListView::AddUnder(BListItem* item, BListItem* superitem)
246 {
247 	if (superitem == NULL)
248 		return AddItem(item);
249 
250 	fFullList.AddItem(item, FullListIndexOf(superitem) + 1);
251 
252 	item->fLevel = superitem->OutlineLevel() + 1;
253 	superitem->fHasSubitems = true;
254 
255 	if (superitem->IsItemVisible() && superitem->IsExpanded()) {
256 		item->SetItemVisible(true);
257 
258 		int32 index = BListView::IndexOf(superitem);
259 
260 		BListView::AddItem(item, index + 1);
261 		Invalidate(LatchRect(ItemFrame(index), superitem->OutlineLevel()));
262 	} else
263 		item->SetItemVisible(false);
264 
265 	return true;
266 }
267 
268 
269 bool
270 BOutlineListView::AddItem(BListItem* item)
271 {
272 	return AddItem(item, FullListCountItems());
273 }
274 
275 
276 bool
277 BOutlineListView::AddItem(BListItem* item, int32 fullListIndex)
278 {
279 	if (fullListIndex < 0)
280 		fullListIndex = 0;
281 	else if (fullListIndex > FullListCountItems())
282 		fullListIndex = FullListCountItems();
283 
284 	if (!fFullList.AddItem(item, fullListIndex))
285 		return false;
286 
287 	// Check if this item is visible, and if it is, add it to the
288 	// other list, too
289 
290 	if (item->fLevel > 0) {
291 		BListItem* super = _SuperitemForIndex(fullListIndex, item->fLevel);
292 		if (super == NULL)
293 			return true;
294 
295 		bool hadSubitems = super->fHasSubitems;
296 		super->fHasSubitems = true;
297 
298 		if (!super->IsItemVisible() || !super->IsExpanded()) {
299 			item->SetItemVisible(false);
300 			return true;
301 		}
302 
303 		if (!hadSubitems)
304 			Invalidate(LatchRect(ItemFrame(IndexOf(super)), super->OutlineLevel()));
305 	}
306 
307 	int32 listIndex = _FindPreviousVisibleIndex(fullListIndex);
308 
309 	if (!BListView::AddItem(item, IndexOf(FullListItemAt(listIndex)) + 1)) {
310 		// adding didn't work out, we need to remove it from the main list again
311 		fFullList.RemoveItem(fullListIndex);
312 		return false;
313 	}
314 
315 	return true;
316 }
317 
318 
319 bool
320 BOutlineListView::AddList(BList* newItems)
321 {
322 	return AddList(newItems, FullListCountItems());
323 }
324 
325 
326 bool
327 BOutlineListView::AddList(BList* newItems, int32 fullListIndex)
328 {
329 	if ((newItems == NULL) || (newItems->CountItems() == 0))
330 		return false;
331 
332 	for (int32 i = 0; i < newItems->CountItems(); i++)
333 		AddItem((BListItem*)newItems->ItemAt(i), fullListIndex + i);
334 
335 	return true;
336 }
337 
338 
339 bool
340 BOutlineListView::RemoveItem(BListItem* item)
341 {
342 	return _RemoveItem(item, FullListIndexOf(item)) != NULL;
343 }
344 
345 
346 BListItem*
347 BOutlineListView::RemoveItem(int32 fullIndex)
348 {
349 	return _RemoveItem(FullListItemAt(fullIndex), fullIndex);
350 }
351 
352 
353 bool
354 BOutlineListView::RemoveItems(int32 fullIndex, int32 count)
355 {
356 	if (fullIndex >= FullListCountItems())
357 		fullIndex = -1;
358 	if (fullIndex < 0)
359 		return false;
360 
361 	// TODO: very bad for performance!!
362 	while (count--) {
363 		BOutlineListView::RemoveItem(fullIndex);
364 	}
365 
366 	return true;
367 }
368 
369 
370 BListItem*
371 BOutlineListView::FullListItemAt(int32 fullListIndex) const
372 {
373 	return (BListItem*)fFullList.ItemAt(fullListIndex);
374 }
375 
376 
377 int32
378 BOutlineListView::FullListIndexOf(BPoint point) const
379 {
380 	int32 index = BListView::IndexOf(point);
381 
382 	if (index > 0)
383 		index = _FullListIndex(index);
384 
385 	return index;
386 }
387 
388 
389 int32
390 BOutlineListView::FullListIndexOf(BListItem* item) const
391 {
392 	return fFullList.IndexOf(item);
393 }
394 
395 
396 BListItem*
397 BOutlineListView::FullListFirstItem() const
398 {
399 	return (BListItem*)fFullList.FirstItem();
400 }
401 
402 
403 BListItem*
404 BOutlineListView::FullListLastItem() const
405 {
406 	return (BListItem*)fFullList.LastItem();
407 }
408 
409 
410 bool
411 BOutlineListView::FullListHasItem(BListItem* item) const
412 {
413 	return fFullList.HasItem(item);
414 }
415 
416 
417 int32
418 BOutlineListView::FullListCountItems() const
419 {
420 	return fFullList.CountItems();
421 }
422 
423 
424 int32
425 BOutlineListView::FullListCurrentSelection(int32 index) const
426 {
427 	int32 i = BListView::CurrentSelection(index);
428 
429 	BListItem* item = BListView::ItemAt(i);
430 	if (item)
431 		return fFullList.IndexOf(item);
432 
433 	return -1;
434 }
435 
436 
437 void
438 BOutlineListView::MakeEmpty()
439 {
440 	fFullList.MakeEmpty();
441 	BListView::MakeEmpty();
442 }
443 
444 
445 bool
446 BOutlineListView::FullListIsEmpty() const
447 {
448 	return fFullList.IsEmpty();
449 }
450 
451 
452 void
453 BOutlineListView::FullListDoForEach(bool(*func)(BListItem* item))
454 {
455 	fFullList.DoForEach(reinterpret_cast<bool (*)(void*)>(func));
456 }
457 
458 
459 void
460 BOutlineListView::FullListDoForEach(bool (*func)(BListItem* item, void* arg),
461 	void* arg)
462 {
463 	fFullList.DoForEach(reinterpret_cast<bool (*)(void*, void*)>(func), arg);
464 }
465 
466 
467 BListItem*
468 BOutlineListView::Superitem(const BListItem* item)
469 {
470 	int32 index = FullListIndexOf((BListItem*)item);
471 	if (index == -1)
472 		return NULL;
473 
474 	return _SuperitemForIndex(index, item->OutlineLevel());
475 }
476 
477 
478 void
479 BOutlineListView::Expand(BListItem* item)
480 {
481 	ExpandOrCollapse(item, true);
482 }
483 
484 
485 void
486 BOutlineListView::Collapse(BListItem* item)
487 {
488 	ExpandOrCollapse(item, false);
489 }
490 
491 
492 bool
493 BOutlineListView::IsExpanded(int32 fullListIndex)
494 {
495 	BListItem* item = FullListItemAt(fullListIndex);
496 	if (!item)
497 		return false;
498 
499 	return item->IsExpanded();
500 }
501 
502 
503 BHandler*
504 BOutlineListView::ResolveSpecifier(BMessage* msg, int32 index,
505 	BMessage* specifier, int32 what, const char* property)
506 {
507 	return BListView::ResolveSpecifier(msg, index, specifier, what, property);
508 }
509 
510 
511 status_t
512 BOutlineListView::GetSupportedSuites(BMessage* data)
513 {
514 	return BListView::GetSupportedSuites(data);
515 }
516 
517 
518 status_t
519 BOutlineListView::Perform(perform_code code, void* _data)
520 {
521 	switch (code) {
522 		case PERFORM_CODE_MIN_SIZE:
523 			((perform_data_min_size*)_data)->return_value
524 				= BOutlineListView::MinSize();
525 			return B_OK;
526 		case PERFORM_CODE_MAX_SIZE:
527 			((perform_data_max_size*)_data)->return_value
528 				= BOutlineListView::MaxSize();
529 			return B_OK;
530 		case PERFORM_CODE_PREFERRED_SIZE:
531 			((perform_data_preferred_size*)_data)->return_value
532 				= BOutlineListView::PreferredSize();
533 			return B_OK;
534 		case PERFORM_CODE_LAYOUT_ALIGNMENT:
535 			((perform_data_layout_alignment*)_data)->return_value
536 				= BOutlineListView::LayoutAlignment();
537 			return B_OK;
538 		case PERFORM_CODE_HAS_HEIGHT_FOR_WIDTH:
539 			((perform_data_has_height_for_width*)_data)->return_value
540 				= BOutlineListView::HasHeightForWidth();
541 			return B_OK;
542 		case PERFORM_CODE_GET_HEIGHT_FOR_WIDTH:
543 		{
544 			perform_data_get_height_for_width* data
545 				= (perform_data_get_height_for_width*)_data;
546 			BOutlineListView::GetHeightForWidth(data->width, &data->min,
547 				&data->max, &data->preferred);
548 			return B_OK;
549 		}
550 		case PERFORM_CODE_SET_LAYOUT:
551 		{
552 			perform_data_set_layout* data = (perform_data_set_layout*)_data;
553 			BOutlineListView::SetLayout(data->layout);
554 			return B_OK;
555 		}
556 		case PERFORM_CODE_LAYOUT_INVALIDATED:
557 		{
558 			perform_data_layout_invalidated* data
559 				= (perform_data_layout_invalidated*)_data;
560 			BOutlineListView::LayoutInvalidated(data->descendants);
561 			return B_OK;
562 		}
563 		case PERFORM_CODE_DO_LAYOUT:
564 		{
565 			BOutlineListView::DoLayout();
566 			return B_OK;
567 		}
568 	}
569 
570 	return BListView::Perform(code, _data);
571 }
572 
573 
574 void
575 BOutlineListView::ResizeToPreferred()
576 {
577 	BListView::ResizeToPreferred();
578 }
579 
580 
581 void
582 BOutlineListView::GetPreferredSize(float* _width, float* _height)
583 {
584 	BListView::GetPreferredSize(_width, _height);
585 }
586 
587 
588 void
589 BOutlineListView::MakeFocus(bool state)
590 {
591 	BListView::MakeFocus(state);
592 }
593 
594 
595 void
596 BOutlineListView::AllAttached()
597 {
598 	BListView::AllAttached();
599 }
600 
601 
602 void
603 BOutlineListView::AllDetached()
604 {
605 	BListView::AllDetached();
606 }
607 
608 
609 void
610 BOutlineListView::DetachedFromWindow()
611 {
612 	BListView::DetachedFromWindow();
613 }
614 
615 
616 void
617 BOutlineListView::FullListSortItems(int (*compareFunc)(const BListItem* a,
618 	const BListItem* b))
619 {
620 	SortItemsUnder(NULL, false, compareFunc);
621 }
622 
623 
624 void
625 BOutlineListView::SortItemsUnder(BListItem* underItem, bool oneLevelOnly,
626 	int (*compareFunc)(const BListItem* a, const BListItem* b))
627 {
628 	// This method is quite complicated: basically, it creates a real tree
629 	// from the items of the full list, sorts them as needed, and then
630 	// populates the entries back into the full and display lists
631 
632 	int32 firstIndex = FullListIndexOf(underItem) + 1;
633 	int32 lastIndex = firstIndex;
634 	BList* tree = _BuildTree(underItem, lastIndex);
635 
636 	_SortTree(tree, oneLevelOnly, compareFunc);
637 
638 	// Populate to the full list
639 	_PopulateTree(tree, fFullList, firstIndex, false);
640 
641 	if (underItem == NULL
642 		|| (underItem->IsItemVisible() && underItem->IsExpanded())) {
643 		// Populate to BListView's list
644 		firstIndex = fList.IndexOf(underItem) + 1;
645 		lastIndex = firstIndex;
646 		_PopulateTree(tree, fList, lastIndex, true);
647 
648 		if (fFirstSelected != -1) {
649 			// update selection hints
650 			fFirstSelected = _CalcFirstSelected(0);
651 			fLastSelected = _CalcLastSelected(CountItems());
652 		}
653 
654 		// only invalidate what may have changed
655 		_RecalcItemTops(firstIndex);
656 		BRect top = ItemFrame(firstIndex);
657 		BRect bottom = ItemFrame(lastIndex - 1);
658 		BRect update(top.left, top.top, bottom.right, bottom.bottom);
659 		Invalidate(update);
660 	}
661 
662 	_DestructTree(tree);
663 }
664 
665 
666 int32
667 BOutlineListView::CountItemsUnder(BListItem* underItem, bool oneLevelOnly) const
668 {
669 	int32 i = FullListIndexOf(underItem);
670 	if (i == -1)
671 		return 0;
672 
673 	++i;
674 	int32 count = 0;
675 	uint32 baseLevel = underItem->OutlineLevel();
676 
677 	for (; i < FullListCountItems(); i++) {
678 		BListItem* item = FullListItemAt(i);
679 
680 		// If we jump out of the subtree, return count
681 		if (item->fLevel <= baseLevel)
682 			return count;
683 
684 		// If the level matches, increase count
685 		if (!oneLevelOnly || item->fLevel == baseLevel + 1)
686 			count++;
687 	}
688 
689 	return count;
690 }
691 
692 
693 BListItem*
694 BOutlineListView::EachItemUnder(BListItem* underItem, bool oneLevelOnly,
695 	BListItem* (*eachFunc)(BListItem* item, void* arg), void* arg)
696 {
697 	int32 i = IndexOf(underItem);
698 	if (i == -1)
699 		return NULL;
700 
701 	while (i < FullListCountItems()) {
702 		BListItem* item = FullListItemAt(i);
703 
704 		// If we jump out of the subtree, return NULL
705 		if (item->fLevel < underItem->OutlineLevel())
706 			return NULL;
707 
708 		// If the level matches, check the index
709 		if (!oneLevelOnly || item->fLevel == underItem->OutlineLevel() + 1) {
710 			item = eachFunc(item, arg);
711 			if (item != NULL)
712 				return item;
713 		}
714 
715 		i++;
716 	}
717 
718 	return NULL;
719 }
720 
721 
722 BListItem*
723 BOutlineListView::ItemUnderAt(BListItem* underItem,
724 	bool oneLevelOnly, int32 index) const
725 {
726 	int32 i = FullListIndexOf(underItem);
727 	if (i == -1)
728 		return NULL;
729 
730 	while (i < FullListCountItems()) {
731 		BListItem* item = FullListItemAt(i);
732 
733 		// If we jump out of the subtree, return NULL
734 		if (item->fLevel < underItem->OutlineLevel())
735 			return NULL;
736 
737 		// If the level matches, check the index
738 		if (!oneLevelOnly || item->fLevel == underItem->OutlineLevel() + 1) {
739 			if (index == 0)
740 				return item;
741 
742 			index--;
743 		}
744 
745 		i++;
746 	}
747 
748 	return NULL;
749 }
750 
751 
752 bool
753 BOutlineListView::DoMiscellaneous(MiscCode code, MiscData* data)
754 {
755 	if (code == B_SWAP_OP)
756 		return _SwapItems(data->swap.a, data->swap.b);
757 
758 	return BListView::DoMiscellaneous(code, data);
759 }
760 
761 
762 void
763 BOutlineListView::MessageReceived(BMessage* msg)
764 {
765 	BListView::MessageReceived(msg);
766 }
767 
768 
769 void BOutlineListView::_ReservedOutlineListView1() {}
770 void BOutlineListView::_ReservedOutlineListView2() {}
771 void BOutlineListView::_ReservedOutlineListView3() {}
772 void BOutlineListView::_ReservedOutlineListView4() {}
773 
774 
775 void
776 BOutlineListView::ExpandOrCollapse(BListItem* item, bool expand)
777 {
778 	if (item->IsExpanded() == expand || !FullListHasItem(item))
779 		return;
780 
781 	item->fExpanded = expand;
782 
783 	// TODO: merge these cases together, they are pretty similar
784 
785 	if (expand) {
786 		uint32 level = item->fLevel;
787 		int32 fullIndex = FullListIndexOf(item);
788 		int32 index = IndexOf(item) + 1;
789 		int32 startIndex = index;
790 		int32 count = FullListCountItems() - fullIndex - 1;
791 		BListItem** items = (BListItem**)fFullList.Items() + fullIndex + 1;
792 
793 		BFont font;
794 		GetFont(&font);
795 		while (count-- > 0) {
796 			item = items[0];
797 			if (item->fLevel <= level)
798 				break;
799 
800 			if (!item->IsItemVisible()) {
801 				// fix selection hints
802 				if (index <= fFirstSelected)
803 					fFirstSelected++;
804 				if (index <= fLastSelected)
805 					fLastSelected++;
806 
807 				fList.AddItem(item, index++);
808 				item->Update(this, &font);
809 				item->SetItemVisible(true);
810 			}
811 
812 			if (item->HasSubitems() && !item->IsExpanded()) {
813 				// Skip hidden children
814 				uint32 subLevel = item->fLevel;
815 				items++;
816 
817 				while (--count > 0 && items[0]->fLevel > subLevel)
818 					items++;
819 			} else
820 				items++;
821 		}
822 		_RecalcItemTops(startIndex);
823 	} else {
824 		// collapse
825 		uint32 level = item->fLevel;
826 		int32 fullIndex = FullListIndexOf(item);
827 		int32 index = IndexOf(item);
828 		int32 startIndex = index;
829 		int32 max = FullListCountItems() - fullIndex - 1;
830 		int32 count = 0;
831 		bool selectionChanged = false;
832 
833 		BListItem** items = (BListItem**)fFullList.Items() + fullIndex + 1;
834 
835 		while (max-- > 0) {
836 			item = items[0];
837 			if (item->fLevel <= level)
838 				break;
839 
840 			if (item->IsItemVisible()) {
841 				fList.RemoveItem(item);
842 				item->SetItemVisible(false);
843 				if (item->IsSelected()) {
844 					selectionChanged = true;
845 					item->Deselect();
846 				}
847 				count++;
848 			}
849 
850 			items++;
851 		}
852 
853 		_RecalcItemTops(startIndex);
854 		// fix selection hints
855 		// if the selected item was just removed by collapsing, select its
856 		// parent
857 		if (ListType() == B_SINGLE_SELECTION_LIST && selectionChanged)
858 			fFirstSelected = fLastSelected = index;
859 		if (index < fFirstSelected && index + count < fFirstSelected) {
860 				// all items removed were higher than the selection range,
861 				// adjust the indexes to correspond to their new visible positions
862 				fFirstSelected -= count;
863 				fLastSelected -= count;
864 		}
865 
866 		int32 maxIndex = fList.CountItems() - 1;
867 		if (fFirstSelected > maxIndex)
868 			fFirstSelected = maxIndex;
869 		if (fLastSelected > maxIndex)
870 			fLastSelected = maxIndex;
871 		if (selectionChanged)
872 			SelectionChanged();
873 	}
874 
875 	_FixupScrollBar();
876 	Invalidate();
877 }
878 
879 
880 BRect
881 BOutlineListView::LatchRect(BRect itemRect, int32 level) const
882 {
883 	float latchDimension = be_plain_font->Size();
884 	float indentWidth = be_control_look->DefaultItemSpacing();
885 	return BRect(itemRect.left, itemRect.top, itemRect.left
886 		+ latchDimension + level * indentWidth, itemRect.bottom);
887 }
888 
889 
890 void
891 BOutlineListView::DrawLatch(BRect itemRect, int32 level, bool collapsed,
892 	bool highlighted, bool misTracked)
893 {
894 	float latchDimension = be_plain_font->Size();
895 	float indentWidth = be_control_look->DefaultItemSpacing();
896 	BPoint itemLoc(itemRect.LeftTop());
897 	float latchOffset = itemRect.Height() / 2 - latchDimension / 2;
898 
899 	BRect rect = BRect(0, 0, latchDimension, latchDimension)
900 		.OffsetBySelf(itemLoc.x, itemLoc.y + latchOffset)
901 		.OffsetBySelf(level * indentWidth, 0);
902 	rgb_color base = ui_color(B_PANEL_BACKGROUND_COLOR);
903 	int32 arrowDirection = collapsed ? BControlLook::B_RIGHT_ARROW
904 		: BControlLook::B_DOWN_ARROW;
905 
906 	be_control_look->DrawArrowShape(this, rect, rect, base,
907 		arrowDirection, 0, B_DARKEN_4_TINT);
908 }
909 
910 
911 void
912 BOutlineListView::DrawItem(BListItem* item, BRect itemRect, bool complete)
913 {
914 	if (item->fHasSubitems)
915 		DrawLatch(itemRect, item->fLevel, !item->IsExpanded(), false, false);
916 
917 	float latchDimension = be_plain_font->Size();
918 	float indentWidth = be_control_look->DefaultItemSpacing();
919 	itemRect.left += latchDimension + item->fLevel * indentWidth;
920 	item->DrawItem(this, itemRect, complete);
921 }
922 
923 
924 int32
925 BOutlineListView::_FullListIndex(int32 index) const
926 {
927 	BListItem* item = ItemAt(index);
928 
929 	if (item == NULL)
930 		return -1;
931 
932 	return FullListIndexOf(item);
933 }
934 
935 
936 void
937 BOutlineListView::_PopulateTree(BList* tree, BList& target,
938 	int32& firstIndex, bool onlyVisible)
939 {
940 	BListItem** items = (BListItem**)target.Items();
941 	int32 count = tree->CountItems();
942 
943 	for (int32 index = 0; index < count; index++) {
944 		BListItem* item = (BListItem*)tree->ItemAtFast(index);
945 
946 		items[firstIndex++] = item;
947 
948 		if (item->HasSubitems() && (!onlyVisible || item->IsExpanded()))
949 			_PopulateTree(item->fTemporaryList, target, firstIndex, onlyVisible);
950 	}
951 }
952 
953 
954 void
955 BOutlineListView::_SortTree(BList* tree, bool oneLevelOnly,
956 	int (*compareFunc)(const BListItem* a, const BListItem* b))
957 {
958 	BListItem** items = (BListItem**)tree->Items();
959 	std::sort(items, items + tree->CountItems(), ListItemComparator(compareFunc));
960 
961 	if (oneLevelOnly)
962 		return;
963 
964 	for (int32 index = tree->CountItems(); index-- > 0;) {
965 		BListItem* item = (BListItem*)tree->ItemAt(index);
966 
967 		if (item->HasSubitems())
968 			_SortTree(item->fTemporaryList, false, compareFunc);
969 	}
970 }
971 
972 
973 void
974 BOutlineListView::_DestructTree(BList* tree)
975 {
976 	for (int32 index = tree->CountItems(); index-- > 0;) {
977 		BListItem* item = (BListItem*)tree->ItemAt(index);
978 
979 		if (item->HasSubitems())
980 			_DestructTree(item->fTemporaryList);
981 	}
982 
983 	delete tree;
984 }
985 
986 
987 BList*
988 BOutlineListView::_BuildTree(BListItem* underItem, int32& fullIndex)
989 {
990 	int32 fullCount = FullListCountItems();
991 	uint32 level = underItem != NULL ? underItem->OutlineLevel() + 1 : 0;
992 	BList* list = new BList;
993 	if (underItem != NULL)
994 		underItem->fTemporaryList = list;
995 
996 	while (fullIndex < fullCount) {
997 		BListItem* item = FullListItemAt(fullIndex);
998 
999 		// If we jump out of the subtree, break out
1000 		if (item->fLevel < level)
1001 			break;
1002 
1003 		// If the level matches, put them into the list
1004 		// (we handle the case of a missing sublevel gracefully)
1005 		list->AddItem(item);
1006 		fullIndex++;
1007 
1008 		if (item->HasSubitems()) {
1009 			// we're going deeper
1010 			_BuildTree(item, fullIndex);
1011 		}
1012 	}
1013 
1014 	return list;
1015 }
1016 
1017 
1018 void
1019 BOutlineListView::_CullInvisibleItems(BList& list)
1020 {
1021 	int32 index = 0;
1022 	while (index < list.CountItems()) {
1023 		if (reinterpret_cast<BListItem*>(list.ItemAt(index))->IsItemVisible())
1024 			++index;
1025 		else
1026 			list.RemoveItem(index);
1027 	}
1028 }
1029 
1030 
1031 bool
1032 BOutlineListView::_SwapItems(int32 first, int32 second)
1033 {
1034 	// same item, do nothing
1035 	if (first == second)
1036 		return true;
1037 
1038 	// fail, first item out of bounds
1039 	if ((first < 0) || (first >= CountItems()))
1040 		return false;
1041 
1042 	// fail, second item out of bounds
1043 	if ((second < 0) || (second >= CountItems()))
1044 		return false;
1045 
1046 	int32 firstIndex = min_c(first, second);
1047 	int32 secondIndex = max_c(first, second);
1048 	BListItem* firstItem = ItemAt(firstIndex);
1049 	BListItem* secondItem = ItemAt(secondIndex);
1050 	BList firstSubItems, secondSubItems;
1051 
1052 	if (Superitem(firstItem) != Superitem(secondItem))
1053 		return false;
1054 	if (!firstItem->IsItemVisible() || !secondItem->IsItemVisible())
1055 		return false;
1056 
1057 	int32 fullFirstIndex = _FullListIndex(firstIndex);
1058 	int32 fullSecondIndex = _FullListIndex(secondIndex);
1059 	_GetSubItems(fFullList, firstSubItems, firstItem, fullFirstIndex + 1);
1060 	_GetSubItems(fFullList, secondSubItems, secondItem, fullSecondIndex + 1);
1061 	_DoSwap(fFullList, fullFirstIndex, fullSecondIndex, &firstSubItems,
1062 		&secondSubItems);
1063 
1064 	_CullInvisibleItems(firstSubItems);
1065 	_CullInvisibleItems(secondSubItems);
1066 	_DoSwap(fList, firstIndex, secondIndex, &firstSubItems,
1067 		&secondSubItems);
1068 
1069 	_RecalcItemTops(firstIndex);
1070 	_RescanSelection(firstIndex, secondIndex + secondSubItems.CountItems());
1071 	Invalidate(Bounds());
1072 	return true;
1073 }
1074 
1075 
1076 /*!	\brief Removes a single item from the list and all of its children.
1077 
1078 	Unlike the BeOS version, this one will actually delete the children, too,
1079 	as there should be no reference left to them. This may cause problems for
1080 	applications that actually take the misbehaviour of the Be classes into
1081 	account.
1082 */
1083 BListItem*
1084 BOutlineListView::_RemoveItem(BListItem* item, int32 fullIndex)
1085 {
1086 	if (item == NULL || fullIndex < 0 || fullIndex >= FullListCountItems())
1087 		return NULL;
1088 
1089 	uint32 level = item->OutlineLevel();
1090 	int32 superIndex;
1091 	BListItem* super = _SuperitemForIndex(fullIndex, level, &superIndex);
1092 
1093 	if (item->IsItemVisible()) {
1094 		// remove children, too
1095 		while (fullIndex + 1 < FullListCountItems()) {
1096 			BListItem* subItem = FullListItemAt(fullIndex + 1);
1097 
1098 			if (subItem->OutlineLevel() <= level)
1099 				break;
1100 
1101 			if (subItem->IsItemVisible())
1102 				BListView::RemoveItem(subItem);
1103 
1104 			fFullList.RemoveItem(fullIndex + 1);
1105 			delete subItem;
1106 		}
1107 		BListView::RemoveItem(item);
1108 	}
1109 
1110 	fFullList.RemoveItem(fullIndex);
1111 
1112 	if (super != NULL) {
1113 		// we might need to change the fHasSubitems field of the parent
1114 		BListItem* child = FullListItemAt(superIndex + 1);
1115 		if (child == NULL || child->OutlineLevel() <= super->OutlineLevel())
1116 			super->fHasSubitems = false;
1117 	}
1118 	return item;
1119 }
1120 
1121 
1122 /*!	Returns the super item before the item specified by \a fullListIndex
1123 	and \a level.
1124 */
1125 BListItem*
1126 BOutlineListView::_SuperitemForIndex(int32 fullListIndex, int32 level,
1127 	int32* _superIndex)
1128 {
1129 	BListItem* item;
1130 	fullListIndex--;
1131 
1132 	while (fullListIndex >= 0) {
1133 		if ((item = FullListItemAt(fullListIndex))->OutlineLevel()
1134 				< (uint32)level) {
1135 			if (_superIndex != NULL)
1136 				*_superIndex = fullListIndex;
1137 			return item;
1138 		}
1139 
1140 		fullListIndex--;
1141 	}
1142 
1143 	return NULL;
1144 }
1145 
1146 
1147 int32
1148 BOutlineListView::_FindPreviousVisibleIndex(int32 fullListIndex)
1149 {
1150 	fullListIndex--;
1151 
1152 	while (fullListIndex >= 0) {
1153 		if (FullListItemAt(fullListIndex)->fVisible)
1154 			return fullListIndex;
1155 
1156 		fullListIndex--;
1157 	}
1158 
1159 	return -1;
1160 }
1161 
1162