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