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