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