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