xref: /haiku/src/kits/interface/OutlineListView.cpp (revision dd2a1e350b303b855a50fd64e6cb55618be1ae6a) 
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 = 0;
701 	uint32 baseLevel = 0;
702 	if (_ItemsUnderSetup(superItem, i, baseLevel) != B_OK)
703 		return 0;
704 
705 	int32 count = 0;
706 	for (; i < FullListCountItems(); i++) {
707 		BListItem* item = FullListItemAt(i);
708 
709 		// If we jump out of the subtree, return count
710 		if (item->fLevel < baseLevel)
711 			return count;
712 
713 		// If the level matches, increase count
714 		if (!oneLevelOnly || item->fLevel == baseLevel)
715 			count++;
716 	}
717 
718 	return count;
719 }
720 
721 
722 BListItem*
723 BOutlineListView::EachItemUnder(BListItem* superItem, bool oneLevelOnly,
724 	BListItem* (*eachFunc)(BListItem* item, void* arg), void* arg)
725 {
726 	int32 i = 0;
727 	uint32 baseLevel = 0;
728 	if (_ItemsUnderSetup(superItem, i, baseLevel) != B_OK)
729 		return NULL;
730 
731 	while (i < FullListCountItems()) {
732 		BListItem* item = FullListItemAt(i);
733 
734 		// If we jump out of the subtree, return NULL
735 		if (item->fLevel < baseLevel)
736 			return NULL;
737 
738 		// If the level matches, check the index
739 		if (!oneLevelOnly || item->fLevel == baseLevel) {
740 			item = eachFunc(item, arg);
741 			if (item != NULL)
742 				return item;
743 		}
744 
745 		i++;
746 	}
747 
748 	return NULL;
749 }
750 
751 
752 BListItem*
753 BOutlineListView::ItemUnderAt(BListItem* superItem, bool oneLevelOnly,
754 	int32 index) const
755 {
756 	int32 i = 0;
757 	uint32 baseLevel = 0;
758 	if (_ItemsUnderSetup(superItem, i, baseLevel) != B_OK)
759 		return NULL;
760 
761 	while (i < FullListCountItems()) {
762 		BListItem* item = FullListItemAt(i);
763 
764 		// If we jump out of the subtree, return NULL
765 		if (item->fLevel < baseLevel)
766 			return NULL;
767 
768 		// If the level matches, check the index
769 		if (!oneLevelOnly || item->fLevel == baseLevel) {
770 			if (index == 0)
771 				return item;
772 
773 			index--;
774 		}
775 
776 		i++;
777 	}
778 
779 	return NULL;
780 }
781 
782 
783 bool
784 BOutlineListView::DoMiscellaneous(MiscCode code, MiscData* data)
785 {
786 	if (code == B_SWAP_OP)
787 		return _SwapItems(data->swap.a, data->swap.b);
788 
789 	return BListView::DoMiscellaneous(code, data);
790 }
791 
792 
793 void
794 BOutlineListView::MessageReceived(BMessage* msg)
795 {
796 	BListView::MessageReceived(msg);
797 }
798 
799 
800 void BOutlineListView::_ReservedOutlineListView1() {}
801 void BOutlineListView::_ReservedOutlineListView2() {}
802 void BOutlineListView::_ReservedOutlineListView3() {}
803 void BOutlineListView::_ReservedOutlineListView4() {}
804 
805 
806 void
807 BOutlineListView::ExpandOrCollapse(BListItem* item, bool expand)
808 {
809 	if (item->IsExpanded() == expand || !FullListHasItem(item))
810 		return;
811 
812 	item->fExpanded = expand;
813 
814 	// TODO: merge these cases together, they are pretty similar
815 
816 	if (expand) {
817 		uint32 level = item->fLevel;
818 		int32 fullListIndex = FullListIndexOf(item);
819 		int32 index = IndexOf(item) + 1;
820 		int32 startIndex = index;
821 		int32 count = FullListCountItems() - fullListIndex - 1;
822 		BListItem** items = (BListItem**)fFullList.Items() + fullListIndex + 1;
823 
824 		BFont font;
825 		GetFont(&font);
826 		while (count-- > 0) {
827 			item = items[0];
828 			if (item->fLevel <= level)
829 				break;
830 
831 			if (!item->IsItemVisible()) {
832 				// fix selection hints
833 				if (index <= fFirstSelected)
834 					fFirstSelected++;
835 				if (index <= fLastSelected)
836 					fLastSelected++;
837 
838 				fList.AddItem(item, index++);
839 				item->Update(this, &font);
840 				item->SetItemVisible(true);
841 			}
842 
843 			if (item->HasSubitems() && !item->IsExpanded()) {
844 				// Skip hidden children
845 				uint32 subLevel = item->fLevel;
846 				items++;
847 
848 				while (count > 0 && items[0]->fLevel > subLevel) {
849 					items++;
850 					count--;
851 				}
852 			} else
853 				items++;
854 		}
855 		_RecalcItemTops(startIndex);
856 	} else {
857 		// collapse
858 		const uint32 level = item->fLevel;
859 		const int32 fullListIndex = FullListIndexOf(item);
860 		const int32 index = IndexOf(item);
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(index);
886 		// fix selection hints
887 		// if the selected item was just removed by collapsing, select its
888 		// parent
889 		if (selectionChanged) {
890 			if (fFirstSelected > index && fFirstSelected <= index + count) {
891 					fFirstSelected = index;
892 			}
893 			if (fLastSelected > index && fLastSelected <= index + count) {
894 				fLastSelected = index;
895 			}
896 		}
897 		if (index + count < fFirstSelected) {
898 				// all items removed were higher than the selection range,
899 				// adjust the indexes to correspond to their new visible positions
900 				fFirstSelected -= count;
901 				fLastSelected -= count;
902 		}
903 
904 		int32 maxIndex = fList.CountItems() - 1;
905 		if (fFirstSelected > maxIndex)
906 			fFirstSelected = maxIndex;
907 
908 		if (fLastSelected > maxIndex)
909 			fLastSelected = maxIndex;
910 
911 		if (selectionChanged)
912 			Select(fFirstSelected, fLastSelected);
913 	}
914 
915 	_FixupScrollBar();
916 	Invalidate();
917 }
918 
919 
920 BRect
921 BOutlineListView::LatchRect(BRect itemRect, int32 level) const
922 {
923 	float latchWidth = be_plain_font->Size();
924 	float latchHeight = be_plain_font->Size();
925 	float indentOffset = level * be_control_look->DefaultItemSpacing();
926 	float heightOffset = itemRect.Height() / 2 - latchHeight / 2;
927 
928 	return BRect(0, 0, latchWidth, latchHeight)
929 		.OffsetBySelf(itemRect.left, itemRect.top)
930 		.OffsetBySelf(indentOffset, heightOffset);
931 }
932 
933 
934 void
935 BOutlineListView::DrawLatch(BRect itemRect, int32 level, bool collapsed,
936 	bool highlighted, bool misTracked)
937 {
938 	BRect latchRect(LatchRect(itemRect, level));
939 	rgb_color base = ui_color(B_PANEL_BACKGROUND_COLOR);
940 	int32 arrowDirection = collapsed ? BControlLook::B_RIGHT_ARROW
941 		: BControlLook::B_DOWN_ARROW;
942 
943 	float tintColor = B_DARKEN_4_TINT;
944 	if (base.red + base.green + base.blue <= 128 * 3) {
945 		tintColor = B_LIGHTEN_2_TINT;
946 	}
947 
948 	be_control_look->DrawArrowShape(this, latchRect, itemRect, base,
949 		arrowDirection, 0, tintColor);
950 }
951 
952 
953 void
954 BOutlineListView::DrawItem(BListItem* item, BRect itemRect, bool complete)
955 {
956 	if (item->fHasSubitems) {
957 		DrawLatch(itemRect, item->fLevel, !item->IsExpanded(),
958 			item->IsSelected() || complete, false);
959 	}
960 
961 	itemRect.left += LatchRect(itemRect, item->fLevel).right;
962 	BListView::DrawItem(item, itemRect, complete);
963 }
964 
965 
966 int32
967 BOutlineListView::_FullListIndex(int32 index) const
968 {
969 	BListItem* item = ItemAt(index);
970 
971 	if (item == NULL)
972 		return -1;
973 
974 	return FullListIndexOf(item);
975 }
976 
977 
978 void
979 BOutlineListView::_PopulateTree(BList* tree, BList& target,
980 	int32& firstIndex, bool onlyVisible)
981 {
982 	BListItem** items = (BListItem**)target.Items();
983 	int32 count = tree->CountItems();
984 
985 	for (int32 index = 0; index < count; index++) {
986 		BListItem* item = (BListItem*)tree->ItemAtFast(index);
987 
988 		items[firstIndex++] = item;
989 
990 		if (item->HasSubitems() && (!onlyVisible || item->IsExpanded())) {
991 			_PopulateTree(item->fTemporaryList, target, firstIndex,
992 				onlyVisible);
993 		}
994 	}
995 }
996 
997 
998 void
999 BOutlineListView::_SortTree(BList* tree, bool oneLevelOnly,
1000 	int (*compareFunc)(const BListItem* a, const BListItem* b))
1001 {
1002 	BListItem** items = (BListItem**)tree->Items();
1003 	std::sort(items, items + tree->CountItems(),
1004 		ListItemComparator(compareFunc));
1005 
1006 	if (oneLevelOnly)
1007 		return;
1008 
1009 	for (int32 index = tree->CountItems(); index-- > 0;) {
1010 		BListItem* item = (BListItem*)tree->ItemAt(index);
1011 
1012 		if (item->HasSubitems())
1013 			_SortTree(item->fTemporaryList, false, compareFunc);
1014 	}
1015 }
1016 
1017 
1018 void
1019 BOutlineListView::_DestructTree(BList* tree)
1020 {
1021 	for (int32 index = tree->CountItems(); index-- > 0;) {
1022 		BListItem* item = (BListItem*)tree->ItemAt(index);
1023 
1024 		if (item->HasSubitems())
1025 			_DestructTree(item->fTemporaryList);
1026 	}
1027 
1028 	delete tree;
1029 }
1030 
1031 
1032 BList*
1033 BOutlineListView::_BuildTree(BListItem* superItem, int32& fullListIndex)
1034 {
1035 	int32 fullCount = FullListCountItems();
1036 	uint32 level = superItem != NULL ? superItem->OutlineLevel() + 1 : 0;
1037 	BList* list = new BList;
1038 	if (superItem != NULL)
1039 		superItem->fTemporaryList = list;
1040 
1041 	while (fullListIndex < fullCount) {
1042 		BListItem* item = FullListItemAt(fullListIndex);
1043 
1044 		// If we jump out of the subtree, break out
1045 		if (item->fLevel < level)
1046 			break;
1047 
1048 		// If the level matches, put them into the list
1049 		// (we handle the case of a missing sublevel gracefully)
1050 		list->AddItem(item);
1051 		fullListIndex++;
1052 
1053 		if (item->HasSubitems()) {
1054 			// we're going deeper
1055 			_BuildTree(item, fullListIndex);
1056 		}
1057 	}
1058 
1059 	return list;
1060 }
1061 
1062 
1063 void
1064 BOutlineListView::_CullInvisibleItems(BList& list)
1065 {
1066 	int32 index = 0;
1067 	while (index < list.CountItems()) {
1068 		if (reinterpret_cast<BListItem*>(list.ItemAt(index))->IsItemVisible())
1069 			++index;
1070 		else
1071 			list.RemoveItem(index);
1072 	}
1073 }
1074 
1075 
1076 bool
1077 BOutlineListView::_SwapItems(int32 first, int32 second)
1078 {
1079 	// same item, do nothing
1080 	if (first == second)
1081 		return true;
1082 
1083 	// fail, first item out of bounds
1084 	if ((first < 0) || (first >= CountItems()))
1085 		return false;
1086 
1087 	// fail, second item out of bounds
1088 	if ((second < 0) || (second >= CountItems()))
1089 		return false;
1090 
1091 	int32 firstIndex = min_c(first, second);
1092 	int32 secondIndex = max_c(first, second);
1093 	BListItem* firstItem = ItemAt(firstIndex);
1094 	BListItem* secondItem = ItemAt(secondIndex);
1095 	BList firstSubItems, secondSubItems;
1096 
1097 	if (Superitem(firstItem) != Superitem(secondItem))
1098 		return false;
1099 
1100 	if (!firstItem->IsItemVisible() || !secondItem->IsItemVisible())
1101 		return false;
1102 
1103 	int32 fullFirstIndex = _FullListIndex(firstIndex);
1104 	int32 fullSecondIndex = _FullListIndex(secondIndex);
1105 	_GetSubItems(fFullList, firstSubItems, firstItem, fullFirstIndex + 1);
1106 	_GetSubItems(fFullList, secondSubItems, secondItem, fullSecondIndex + 1);
1107 	_DoSwap(fFullList, fullFirstIndex, fullSecondIndex, &firstSubItems,
1108 		&secondSubItems);
1109 
1110 	_CullInvisibleItems(firstSubItems);
1111 	_CullInvisibleItems(secondSubItems);
1112 	_DoSwap(fList, firstIndex, secondIndex, &firstSubItems,
1113 		&secondSubItems);
1114 
1115 	_RecalcItemTops(firstIndex);
1116 	_RescanSelection(firstIndex, secondIndex + secondSubItems.CountItems());
1117 	Invalidate(Bounds());
1118 
1119 	return true;
1120 }
1121 
1122 
1123 /*!	\brief Removes a single item from the list and all of its children.
1124 
1125 	Unlike the BeOS version, this one will actually delete the children, too,
1126 	as there should be no reference left to them. This may cause problems for
1127 	applications that actually take the misbehaviour of the Be classes into
1128 	account.
1129 */
1130 BListItem*
1131 BOutlineListView::_RemoveItem(BListItem* item, int32 fullListIndex)
1132 {
1133 	if (item == NULL || fullListIndex < 0
1134 		|| fullListIndex >= FullListCountItems()) {
1135 		return NULL;
1136 	}
1137 
1138 	uint32 level = item->OutlineLevel();
1139 	int32 superIndex;
1140 	BListItem* super = _SuperitemForIndex(fullListIndex, level, &superIndex);
1141 
1142 	if (item->IsItemVisible()) {
1143 		// remove children, too
1144 		while (fullListIndex + 1 < FullListCountItems()) {
1145 			BListItem* subItem = FullListItemAt(fullListIndex + 1);
1146 
1147 			if (subItem->OutlineLevel() <= level)
1148 				break;
1149 
1150 			if (subItem->IsItemVisible())
1151 				BListView::RemoveItem(subItem);
1152 
1153 			fFullList.RemoveItem(fullListIndex + 1);
1154 			delete subItem;
1155 		}
1156 		BListView::RemoveItem(item);
1157 	}
1158 
1159 	fFullList.RemoveItem(fullListIndex);
1160 
1161 	if (super != NULL) {
1162 		// we might need to change the fHasSubitems field of the parent
1163 		BListItem* child = FullListItemAt(superIndex + 1);
1164 		if (child == NULL || child->OutlineLevel() <= super->OutlineLevel())
1165 			super->fHasSubitems = false;
1166 	}
1167 
1168 	return item;
1169 }
1170 
1171 
1172 /*!	Returns the super item before the item specified by \a fullListIndex
1173 	and \a level.
1174 */
1175 BListItem*
1176 BOutlineListView::_SuperitemForIndex(int32 fullListIndex, int32 level,
1177 	int32* _superIndex)
1178 {
1179 	BListItem* item;
1180 	fullListIndex--;
1181 
1182 	while (fullListIndex >= 0) {
1183 		if ((item = FullListItemAt(fullListIndex))->OutlineLevel()
1184 				< (uint32)level) {
1185 			if (_superIndex != NULL)
1186 				*_superIndex = fullListIndex;
1187 			return item;
1188 		}
1189 
1190 		fullListIndex--;
1191 	}
1192 
1193 	return NULL;
1194 }
1195 
1196 
1197 int32
1198 BOutlineListView::_FindPreviousVisibleIndex(int32 fullListIndex)
1199 {
1200 	fullListIndex--;
1201 
1202 	while (fullListIndex >= 0) {
1203 		if (FullListItemAt(fullListIndex)->fVisible)
1204 			return fullListIndex;
1205 
1206 		fullListIndex--;
1207 	}
1208 
1209 	return -1;
1210 }
1211 
1212 
1213 status_t
1214 BOutlineListView::_ItemsUnderSetup(BListItem* superItem, int32& startIndex, uint32& baseLevel) const
1215 {
1216 	if (superItem != NULL) {
1217 		startIndex = FullListIndexOf(superItem) + 1;
1218 		if (startIndex == 0)
1219 			return B_ENTRY_NOT_FOUND;
1220 		baseLevel = superItem->OutlineLevel() + 1;
1221 	} else {
1222 		startIndex = 0;
1223 		baseLevel = 0;
1224 	}
1225 	return B_OK;
1226 }
1227