/*
 * Copyright 2001-2013 Haiku, Inc. All rights reserved.
 * Distributed under the terms of the MIT License.
 *
 * Authors:
 *              Marc Flerackers (mflerackers@androme.be)
 *              Axel Dörfler, axeld@pinc-software.de
 *              Rene Gollent (rene@gollent.com)
 *              Philippe Saint-Pierre, stpere@gmail.com
 *              John Scipione, jscipione@gmail.com
 */


//! BOutlineListView represents a "nestable" list view.


#include <OutlineListView.h>

#include <algorithm>

#include <stdio.h>
#include <stdlib.h>

#include <ControlLook.h>
#include <Window.h>

#include <binary_compatibility/Interface.h>


typedef int (*compare_func)(const BListItem* a, const BListItem* b);


struct ListItemComparator {
        ListItemComparator(compare_func compareFunc)
                :
                fCompareFunc(compareFunc)
        {
        }

        bool operator()(const BListItem* a, const BListItem* b) const
        {
                return fCompareFunc(a, b) < 0;
        }

private:
        compare_func    fCompareFunc;
};


static void
_GetSubItems(BList& sourceList, BList& destList, BListItem* parent, int32 start)
{
        for (int32 i = start; i < sourceList.CountItems(); i++) {
                BListItem* item = (BListItem*)sourceList.ItemAt(i);
                if (item->OutlineLevel() <= parent->OutlineLevel())
                        break;
                destList.AddItem(item);
        }
}


static void
_DoSwap(BList& list, int32 firstIndex, int32 secondIndex, BList* firstItems,
        BList* secondItems)
{
        BListItem* item = (BListItem*)list.ItemAt(firstIndex);
        list.SwapItems(firstIndex, secondIndex);
        list.RemoveItems(secondIndex + 1, secondItems->CountItems());
        list.RemoveItems(firstIndex + 1, firstItems->CountItems());
        list.AddList(secondItems, firstIndex + 1);
        int32 newIndex = list.IndexOf(item);
        if (newIndex + 1 < list.CountItems())
                list.AddList(firstItems, newIndex + 1);
        else
                list.AddList(firstItems);
}


//      #pragma mark - BOutlineListView


BOutlineListView::BOutlineListView(BRect frame, const char* name,
        list_view_type type, uint32 resizingMode, uint32 flags)
        :
        BListView(frame, name, type, resizingMode, flags)
{
}


BOutlineListView::BOutlineListView(const char* name, list_view_type type,
        uint32 flags)
        :
        BListView(name, type, flags)
{
}


BOutlineListView::BOutlineListView(BMessage* archive)
        :
        BListView(archive)
{
        int32 i = 0;
        BMessage subData;
        while (archive->FindMessage("_l_full_items", i++, &subData) == B_OK) {
                BArchivable* object = instantiate_object(&subData);
                if (!object)
                        continue;

                BListItem* item = dynamic_cast<BListItem*>(object);
                if (item)
                        AddItem(item);
        }
}


BOutlineListView::~BOutlineListView()
{
        fFullList.MakeEmpty();
}


BArchivable*
BOutlineListView::Instantiate(BMessage* archive)
{
        if (validate_instantiation(archive, "BOutlineListView"))
                return new BOutlineListView(archive);

        return NULL;
}


status_t
BOutlineListView::Archive(BMessage* archive, bool deep) const
{
        // Note: We can't call the BListView Archive function here, as we are also
        // interested in subitems BOutlineListView can have. They are even stored
        // with a different field name (_l_full_items vs. _l_items).

        status_t status = BView::Archive(archive, deep);
        if (status != B_OK)
                return status;

        status = archive->AddInt32("_lv_type", fListType);
        if (status == B_OK && deep) {
                int32 i = 0;
                BListItem* item = NULL;
                while ((item = static_cast<BListItem*>(fFullList.ItemAt(i++)))) {
                        BMessage subData;
                        status = item->Archive(&subData, true);
                        if (status >= B_OK)
                                status = archive->AddMessage("_l_full_items", &subData);

                        if (status < B_OK)
                                break;
                }
        }

        if (status >= B_OK && InvocationMessage() != NULL)
                status = archive->AddMessage("_msg", InvocationMessage());

        if (status == B_OK && fSelectMessage != NULL)
                status = archive->AddMessage("_2nd_msg", fSelectMessage);

        return status;
}


void
BOutlineListView::MouseDown(BPoint where)
{
        MakeFocus();

        int32 index = IndexOf(where);

        if (index != -1) {
                BListItem* item = ItemAt(index);

                if (item->fHasSubitems
                        && LatchRect(ItemFrame(index), item->fLevel).Contains(where)) {
                        if (item->IsExpanded())
                                Collapse(item);
                        else
                                Expand(item);
                } else
                        BListView::MouseDown(where);
        }
}


void
BOutlineListView::KeyDown(const char* bytes, int32 numBytes)
{
        if (numBytes == 1) {
                int32 currentSel = CurrentSelection();
                switch (bytes[0]) {
                        case B_RIGHT_ARROW:
                        {
                                BListItem* item = ItemAt(currentSel);
                                if (item && item->fHasSubitems) {
                                        if (!item->IsExpanded())
                                                Expand(item);
                                        else {
                                                Select(currentSel + 1);
                                                ScrollToSelection();
                                        }
                                }
                                return;
                        }

                        case B_LEFT_ARROW:
                        {
                                BListItem* item = ItemAt(currentSel);
                                if (item) {
                                        if (item->fHasSubitems && item->IsExpanded())
                                                Collapse(item);
                                        else {
                                                item = Superitem(item);
                                                if (item) {
                                                        Select(IndexOf(item));
                                                        ScrollToSelection();
                                                }
                                        }
                                }
                                return;
                        }
                }
        }

        BListView::KeyDown(bytes, numBytes);
}


void
BOutlineListView::FrameMoved(BPoint newPosition)
{
        BListView::FrameMoved(newPosition);
}


void
BOutlineListView::FrameResized(float newWidth, float newHeight)
{
        BListView::FrameResized(newWidth, newHeight);
}


void
BOutlineListView::MouseUp(BPoint where)
{
        BListView::MouseUp(where);
}


bool
BOutlineListView::AddUnder(BListItem* item, BListItem* superItem)
{
        if (superItem == NULL)
                return AddItem(item);

        fFullList.AddItem(item, FullListIndexOf(superItem) + 1);

        item->fLevel = superItem->OutlineLevel() + 1;
        superItem->fHasSubitems = true;

        if (superItem->IsItemVisible() && superItem->IsExpanded()) {
                item->SetItemVisible(true);

                int32 index = BListView::IndexOf(superItem);

                BListView::AddItem(item, index + 1);
                Invalidate(LatchRect(ItemFrame(index), superItem->OutlineLevel()));
        } else
                item->SetItemVisible(false);

        return true;
}


bool
BOutlineListView::AddItem(BListItem* item)
{
        return AddItem(item, FullListCountItems());
}


bool
BOutlineListView::AddItem(BListItem* item, int32 fullListIndex)
{
        if (fullListIndex < 0)
                fullListIndex = 0;
        else if (fullListIndex > FullListCountItems())
                fullListIndex = FullListCountItems();

        if (!fFullList.AddItem(item, fullListIndex))
                return false;

        // Check if this item is visible, and if it is, add it to the
        // other list, too

        if (item->fLevel > 0) {
                BListItem* super = _SuperitemForIndex(fullListIndex, item->fLevel);
                if (super == NULL)
                        return true;

                bool hadSubitems = super->fHasSubitems;
                super->fHasSubitems = true;

                if (!super->IsItemVisible() || !super->IsExpanded()) {
                        item->SetItemVisible(false);
                        return true;
                }

                if (!hadSubitems) {
                        Invalidate(LatchRect(ItemFrame(IndexOf(super)),
                                super->OutlineLevel()));
                }
        }

        int32 listIndex = _FindPreviousVisibleIndex(fullListIndex);

        if (!BListView::AddItem(item, IndexOf(FullListItemAt(listIndex)) + 1)) {
                // adding didn't work out, we need to remove it from the main list again
                fFullList.RemoveItem(fullListIndex);
                return false;
        }

        return true;
}


bool
BOutlineListView::AddList(BList* newItems)
{
        return AddList(newItems, FullListCountItems());
}


bool
BOutlineListView::AddList(BList* newItems, int32 fullListIndex)
{
        if ((newItems == NULL) || (newItems->CountItems() == 0))
                return false;

        for (int32 i = 0; i < newItems->CountItems(); i++)
                AddItem((BListItem*)newItems->ItemAt(i), fullListIndex + i);

        return true;
}


bool
BOutlineListView::RemoveItem(BListItem* item)
{
        return _RemoveItem(item, FullListIndexOf(item)) != NULL;
}


BListItem*
BOutlineListView::RemoveItem(int32 fullListIndex)
{
        return _RemoveItem(FullListItemAt(fullListIndex), fullListIndex);
}


bool
BOutlineListView::RemoveItems(int32 fullListIndex, int32 count)
{
        if (fullListIndex >= FullListCountItems())
                fullListIndex = -1;
        if (fullListIndex < 0)
                return false;

        // TODO: very bad for performance!!
        while (count--)
                BOutlineListView::RemoveItem(fullListIndex);

        return true;
}


BListItem*
BOutlineListView::FullListItemAt(int32 fullListIndex) const
{
        return (BListItem*)fFullList.ItemAt(fullListIndex);
}


int32
BOutlineListView::FullListIndexOf(BPoint where) const
{
        int32 index = BListView::IndexOf(where);

        if (index > 0)
                index = _FullListIndex(index);

        return index;
}


int32
BOutlineListView::FullListIndexOf(BListItem* item) const
{
        return fFullList.IndexOf(item);
}


BListItem*
BOutlineListView::FullListFirstItem() const
{
        return (BListItem*)fFullList.FirstItem();
}


BListItem*
BOutlineListView::FullListLastItem() const
{
        return (BListItem*)fFullList.LastItem();
}


bool
BOutlineListView::FullListHasItem(BListItem* item) const
{
        return fFullList.HasItem(item);
}


int32
BOutlineListView::FullListCountItems() const
{
        return fFullList.CountItems();
}


int32
BOutlineListView::FullListCurrentSelection(int32 index) const
{
        int32 i = BListView::CurrentSelection(index);

        BListItem* item = BListView::ItemAt(i);
        if (item)
                return fFullList.IndexOf(item);

        return -1;
}


void
BOutlineListView::MakeEmpty()
{
        fFullList.MakeEmpty();
        BListView::MakeEmpty();
}


bool
BOutlineListView::FullListIsEmpty() const
{
        return fFullList.IsEmpty();
}


void
BOutlineListView::FullListDoForEach(bool(*func)(BListItem* item))
{
        fFullList.DoForEach(reinterpret_cast<bool (*)(void*)>(func));
}


void
BOutlineListView::FullListDoForEach(bool (*func)(BListItem* item, void* arg),
        void* arg)
{
        fFullList.DoForEach(reinterpret_cast<bool (*)(void*, void*)>(func), arg);
}


BListItem*
BOutlineListView::Superitem(const BListItem* item)
{
        int32 index = FullListIndexOf((BListItem*)item);
        if (index == -1)
                return NULL;

        return _SuperitemForIndex(index, item->OutlineLevel());
}


void
BOutlineListView::Expand(BListItem* item)
{
        ExpandOrCollapse(item, true);
}


void
BOutlineListView::Collapse(BListItem* item)
{
        ExpandOrCollapse(item, false);
}


bool
BOutlineListView::IsExpanded(int32 fullListIndex)
{
        BListItem* item = FullListItemAt(fullListIndex);
        if (!item)
                return false;

        return item->IsExpanded();
}


BHandler*
BOutlineListView::ResolveSpecifier(BMessage* message, int32 index,
        BMessage* specifier, int32 what, const char* property)
{
        return BListView::ResolveSpecifier(message, index, specifier, what,
                property);
}


status_t
BOutlineListView::GetSupportedSuites(BMessage* data)
{
        return BListView::GetSupportedSuites(data);
}


status_t
BOutlineListView::Perform(perform_code code, void* _data)
{
        switch (code) {
                case PERFORM_CODE_MIN_SIZE:
                        ((perform_data_min_size*)_data)->return_value
                                = BOutlineListView::MinSize();
                        return B_OK;
                case PERFORM_CODE_MAX_SIZE:
                        ((perform_data_max_size*)_data)->return_value
                                = BOutlineListView::MaxSize();
                        return B_OK;
                case PERFORM_CODE_PREFERRED_SIZE:
                        ((perform_data_preferred_size*)_data)->return_value
                                = BOutlineListView::PreferredSize();
                        return B_OK;
                case PERFORM_CODE_LAYOUT_ALIGNMENT:
                        ((perform_data_layout_alignment*)_data)->return_value
                                = BOutlineListView::LayoutAlignment();
                        return B_OK;
                case PERFORM_CODE_HAS_HEIGHT_FOR_WIDTH:
                        ((perform_data_has_height_for_width*)_data)->return_value
                                = BOutlineListView::HasHeightForWidth();
                        return B_OK;
                case PERFORM_CODE_GET_HEIGHT_FOR_WIDTH:
                {
                        perform_data_get_height_for_width* data
                                = (perform_data_get_height_for_width*)_data;
                        BOutlineListView::GetHeightForWidth(data->width, &data->min,
                                &data->max, &data->preferred);
                        return B_OK;
                }
                case PERFORM_CODE_SET_LAYOUT:
                {
                        perform_data_set_layout* data = (perform_data_set_layout*)_data;
                        BOutlineListView::SetLayout(data->layout);
                        return B_OK;
                }
                case PERFORM_CODE_LAYOUT_INVALIDATED:
                {
                        perform_data_layout_invalidated* data
                                = (perform_data_layout_invalidated*)_data;
                        BOutlineListView::LayoutInvalidated(data->descendants);
                        return B_OK;
                }
                case PERFORM_CODE_DO_LAYOUT:
                {
                        BOutlineListView::DoLayout();
                        return B_OK;
                }
        }

        return BListView::Perform(code, _data);
}


void
BOutlineListView::ResizeToPreferred()
{
        BListView::ResizeToPreferred();
}


void
BOutlineListView::GetPreferredSize(float* _width, float* _height)
{
        int32 count = CountItems();

        if (count > 0) {
                float maxWidth = 0.0;
                for (int32 i = 0; i < count; i++) {
                        // The item itself does not take his OutlineLevel into account, so
                        // we must make up for that. Also add space for the latch.
                        float itemWidth = ItemAt(i)->Width() + be_plain_font->Size()
                                + (ItemAt(i)->OutlineLevel() + 1)
                                        * be_control_look->DefaultItemSpacing();
                        if (itemWidth > maxWidth)
                                maxWidth = itemWidth;
                }

                if (_width != NULL)
                        *_width = maxWidth;
                if (_height != NULL)
                        *_height = ItemAt(count - 1)->Bottom();
        } else
                BView::GetPreferredSize(_width, _height);
}


void
BOutlineListView::MakeFocus(bool state)
{
        BListView::MakeFocus(state);
}


void
BOutlineListView::AllAttached()
{
        BListView::AllAttached();
}


void
BOutlineListView::AllDetached()
{
        BListView::AllDetached();
}


void
BOutlineListView::DetachedFromWindow()
{
        BListView::DetachedFromWindow();
}


void
BOutlineListView::FullListSortItems(int (*compareFunc)(const BListItem* a,
        const BListItem* b))
{
        SortItemsUnder(NULL, false, compareFunc);
}


void
BOutlineListView::SortItemsUnder(BListItem* superItem, bool oneLevelOnly,
        int (*compareFunc)(const BListItem* a, const BListItem* b))
{
        // This method is quite complicated: basically, it creates a real tree
        // from the items of the full list, sorts them as needed, and then
        // populates the entries back into the full and display lists

        int32 firstIndex = FullListIndexOf(superItem) + 1;
        int32 lastIndex = firstIndex;
        BList* tree = _BuildTree(superItem, lastIndex);

        _SortTree(tree, oneLevelOnly, compareFunc);

        // Populate to the full list
        _PopulateTree(tree, fFullList, firstIndex, false);

        if (superItem == NULL
                || (superItem->IsItemVisible() && superItem->IsExpanded())) {
                // Populate to BListView's list
                firstIndex = fList.IndexOf(superItem) + 1;
                lastIndex = firstIndex;
                _PopulateTree(tree, fList, lastIndex, true);

                if (fFirstSelected != -1) {
                        // update selection hints
                        fFirstSelected = _CalcFirstSelected(0);
                        fLastSelected = _CalcLastSelected(CountItems());
                }

                // only invalidate what may have changed
                _RecalcItemTops(firstIndex);
                BRect top = ItemFrame(firstIndex);
                BRect bottom = ItemFrame(lastIndex - 1);
                BRect update(top.left, top.top, bottom.right, bottom.bottom);
                Invalidate(update);
        }

        _DestructTree(tree);
}


int32
BOutlineListView::CountItemsUnder(BListItem* superItem, bool oneLevelOnly) const
{
        int32 i = 0;
        uint32 baseLevel = 0;
        if (_ItemsUnderSetup(superItem, i, baseLevel) != B_OK)
                return 0;

        int32 count = 0;
        for (; i < FullListCountItems(); i++) {
                BListItem* item = FullListItemAt(i);

                // If we jump out of the subtree, return count
                if (item->fLevel < baseLevel)
                        return count;

                // If the level matches, increase count
                if (!oneLevelOnly || item->fLevel == baseLevel)
                        count++;
        }

        return count;
}


BListItem*
BOutlineListView::EachItemUnder(BListItem* superItem, bool oneLevelOnly,
        BListItem* (*eachFunc)(BListItem* item, void* arg), void* arg)
{
        int32 i = 0;
        uint32 baseLevel = 0;
        if (_ItemsUnderSetup(superItem, i, baseLevel) != B_OK)
                return NULL;

        while (i < FullListCountItems()) {
                BListItem* item = FullListItemAt(i);

                // If we jump out of the subtree, return NULL
                if (item->fLevel < baseLevel)
                        return NULL;

                // If the level matches, check the index
                if (!oneLevelOnly || item->fLevel == baseLevel) {
                        item = eachFunc(item, arg);
                        if (item != NULL)
                                return item;
                }

                i++;
        }

        return NULL;
}


BListItem*
BOutlineListView::ItemUnderAt(BListItem* superItem, bool oneLevelOnly,
        int32 index) const
{
        int32 i = 0;
        uint32 baseLevel = 0;
        if (_ItemsUnderSetup(superItem, i, baseLevel) != B_OK)
                return NULL;

        while (i < FullListCountItems()) {
                BListItem* item = FullListItemAt(i);

                // If we jump out of the subtree, return NULL
                if (item->fLevel < baseLevel)
                        return NULL;

                // If the level matches, check the index
                if (!oneLevelOnly || item->fLevel == baseLevel) {
                        if (index == 0)
                                return item;

                        index--;
                }

                i++;
        }

        return NULL;
}


bool
BOutlineListView::DoMiscellaneous(MiscCode code, MiscData* data)
{
        if (code == B_SWAP_OP)
                return _SwapItems(data->swap.a, data->swap.b);

        return BListView::DoMiscellaneous(code, data);
}


void
BOutlineListView::MessageReceived(BMessage* msg)
{
        BListView::MessageReceived(msg);
}


void BOutlineListView::_ReservedOutlineListView1() {}
void BOutlineListView::_ReservedOutlineListView2() {}
void BOutlineListView::_ReservedOutlineListView3() {}
void BOutlineListView::_ReservedOutlineListView4() {}


void
BOutlineListView::ExpandOrCollapse(BListItem* item, bool expand)
{
        if (item->IsExpanded() == expand || !FullListHasItem(item))
                return;

        item->fExpanded = expand;

        // TODO: merge these cases together, they are pretty similar

        if (expand) {
                uint32 level = item->fLevel;
                int32 fullListIndex = FullListIndexOf(item);
                int32 index = IndexOf(item) + 1;
                int32 startIndex = index;
                int32 count = FullListCountItems() - fullListIndex - 1;
                BListItem** items = (BListItem**)fFullList.Items() + fullListIndex + 1;

                BFont font;
                GetFont(&font);
                while (count-- > 0) {
                        item = items[0];
                        if (item->fLevel <= level)
                                break;

                        if (!item->IsItemVisible()) {
                                // fix selection hints
                                if (index <= fFirstSelected)
                                        fFirstSelected++;
                                if (index <= fLastSelected)
                                        fLastSelected++;

                                fList.AddItem(item, index++);
                                item->Update(this, &font);
                                item->SetItemVisible(true);
                        }

                        if (item->HasSubitems() && !item->IsExpanded()) {
                                // Skip hidden children
                                uint32 subLevel = item->fLevel;
                                items++;

                                while (count > 0 && items[0]->fLevel > subLevel) {
                                        items++;
                                        count--;
                                }
                        } else
                                items++;
                }
                _RecalcItemTops(startIndex);
        } else {
                // collapse
                const uint32 level = item->fLevel;
                const int32 fullListIndex = FullListIndexOf(item);
                const int32 index = IndexOf(item);
                int32 max = FullListCountItems() - fullListIndex - 1;
                int32 count = 0;
                bool selectionChanged = false;

                BListItem** items = (BListItem**)fFullList.Items() + fullListIndex + 1;

                while (max-- > 0) {
                        item = items[0];
                        if (item->fLevel <= level)
                                break;

                        if (item->IsItemVisible()) {
                                fList.RemoveItem(item);
                                item->SetItemVisible(false);
                                if (item->IsSelected()) {
                                        selectionChanged = true;
                                        item->Deselect();
                                }
                                count++;
                        }

                        items++;
                }

                _RecalcItemTops(index);
                // fix selection hints
                // if the selected item was just removed by collapsing, select its
                // parent
                if (selectionChanged) {
                        if (fFirstSelected > index && fFirstSelected <= index + count) {
                                        fFirstSelected = index;
                        }
                        if (fLastSelected > index && fLastSelected <= index + count) {
                                fLastSelected = index;
                        }
                }
                if (index + count < fFirstSelected) {
                                // all items removed were higher than the selection range,
                                // adjust the indexes to correspond to their new visible positions
                                fFirstSelected -= count;
                                fLastSelected -= count;
                }

                int32 maxIndex = fList.CountItems() - 1;
                if (fFirstSelected > maxIndex)
                        fFirstSelected = maxIndex;

                if (fLastSelected > maxIndex)
                        fLastSelected = maxIndex;

                if (selectionChanged)
                        Select(fFirstSelected, fLastSelected);
        }

        _FixupScrollBar();
        Invalidate();
}


BRect
BOutlineListView::LatchRect(BRect itemRect, int32 level) const
{
        float latchWidth = be_plain_font->Size();
        float latchHeight = be_plain_font->Size();
        float indentOffset = level * be_control_look->DefaultItemSpacing();
        float heightOffset = itemRect.Height() / 2 - latchHeight / 2;

        return BRect(0, 0, latchWidth, latchHeight)
                .OffsetBySelf(itemRect.left, itemRect.top)
                .OffsetBySelf(indentOffset, heightOffset);
}


void
BOutlineListView::DrawLatch(BRect itemRect, int32 level, bool collapsed,
        bool highlighted, bool misTracked)
{
        BRect latchRect(LatchRect(itemRect, level));
        rgb_color base = ui_color(B_PANEL_BACKGROUND_COLOR);
        int32 arrowDirection = collapsed ? BControlLook::B_RIGHT_ARROW
                : BControlLook::B_DOWN_ARROW;

        float tintColor = B_DARKEN_4_TINT;
        if (base.red + base.green + base.blue <= 128 * 3) {
                tintColor = B_LIGHTEN_2_TINT;
        }

        be_control_look->DrawArrowShape(this, latchRect, itemRect, base,
                arrowDirection, 0, tintColor);
}


void
BOutlineListView::DrawItem(BListItem* item, BRect itemRect, bool complete)
{
        if (item->fHasSubitems) {
                DrawLatch(itemRect, item->fLevel, !item->IsExpanded(),
                        item->IsSelected() || complete, false);
        }

        itemRect.left += LatchRect(itemRect, item->fLevel).right;
        BListView::DrawItem(item, itemRect, complete);
}


int32
BOutlineListView::_FullListIndex(int32 index) const
{
        BListItem* item = ItemAt(index);

        if (item == NULL)
                return -1;

        return FullListIndexOf(item);
}


void
BOutlineListView::_PopulateTree(BList* tree, BList& target,
        int32& firstIndex, bool onlyVisible)
{
        BListItem** items = (BListItem**)target.Items();
        int32 count = tree->CountItems();

        for (int32 index = 0; index < count; index++) {
                BListItem* item = (BListItem*)tree->ItemAtFast(index);

                items[firstIndex++] = item;

                if (item->HasSubitems() && (!onlyVisible || item->IsExpanded())) {
                        _PopulateTree(item->fTemporaryList, target, firstIndex,
                                onlyVisible);
                }
        }
}


void
BOutlineListView::_SortTree(BList* tree, bool oneLevelOnly,
        int (*compareFunc)(const BListItem* a, const BListItem* b))
{
        BListItem** items = (BListItem**)tree->Items();
        std::sort(items, items + tree->CountItems(),
                ListItemComparator(compareFunc));

        if (oneLevelOnly)
                return;

        for (int32 index = tree->CountItems(); index-- > 0;) {
                BListItem* item = (BListItem*)tree->ItemAt(index);

                if (item->HasSubitems())
                        _SortTree(item->fTemporaryList, false, compareFunc);
        }
}


void
BOutlineListView::_DestructTree(BList* tree)
{
        for (int32 index = tree->CountItems(); index-- > 0;) {
                BListItem* item = (BListItem*)tree->ItemAt(index);

                if (item->HasSubitems())
                        _DestructTree(item->fTemporaryList);
        }

        delete tree;
}


BList*
BOutlineListView::_BuildTree(BListItem* superItem, int32& fullListIndex)
{
        int32 fullCount = FullListCountItems();
        uint32 level = superItem != NULL ? superItem->OutlineLevel() + 1 : 0;
        BList* list = new BList;
        if (superItem != NULL)
                superItem->fTemporaryList = list;

        while (fullListIndex < fullCount) {
                BListItem* item = FullListItemAt(fullListIndex);

                // If we jump out of the subtree, break out
                if (item->fLevel < level)
                        break;

                // If the level matches, put them into the list
                // (we handle the case of a missing sublevel gracefully)
                list->AddItem(item);
                fullListIndex++;

                if (item->HasSubitems()) {
                        // we're going deeper
                        _BuildTree(item, fullListIndex);
                }
        }

        return list;
}


void
BOutlineListView::_CullInvisibleItems(BList& list)
{
        int32 index = 0;
        while (index < list.CountItems()) {
                if (reinterpret_cast<BListItem*>(list.ItemAt(index))->IsItemVisible())
                        ++index;
                else
                        list.RemoveItem(index);
        }
}


bool
BOutlineListView::_SwapItems(int32 first, int32 second)
{
        // same item, do nothing
        if (first == second)
                return true;

        // fail, first item out of bounds
        if ((first < 0) || (first >= CountItems()))
                return false;

        // fail, second item out of bounds
        if ((second < 0) || (second >= CountItems()))
                return false;

        int32 firstIndex = min_c(first, second);
        int32 secondIndex = max_c(first, second);
        BListItem* firstItem = ItemAt(firstIndex);
        BListItem* secondItem = ItemAt(secondIndex);
        BList firstSubItems, secondSubItems;

        if (Superitem(firstItem) != Superitem(secondItem))
                return false;

        if (!firstItem->IsItemVisible() || !secondItem->IsItemVisible())
                return false;

        int32 fullFirstIndex = _FullListIndex(firstIndex);
        int32 fullSecondIndex = _FullListIndex(secondIndex);
        _GetSubItems(fFullList, firstSubItems, firstItem, fullFirstIndex + 1);
        _GetSubItems(fFullList, secondSubItems, secondItem, fullSecondIndex + 1);
        _DoSwap(fFullList, fullFirstIndex, fullSecondIndex, &firstSubItems,
                &secondSubItems);

        _CullInvisibleItems(firstSubItems);
        _CullInvisibleItems(secondSubItems);
        _DoSwap(fList, firstIndex, secondIndex, &firstSubItems,
                &secondSubItems);

        _RecalcItemTops(firstIndex);
        _RescanSelection(firstIndex, secondIndex + secondSubItems.CountItems());
        Invalidate(Bounds());

        return true;
}


/*!     \brief Removes a single item from the list and all of its children.

        Unlike the BeOS version, this one will actually delete the children, too,
        as there should be no reference left to them. This may cause problems for
        applications that actually take the misbehaviour of the Be classes into
        account.
*/
BListItem*
BOutlineListView::_RemoveItem(BListItem* item, int32 fullListIndex)
{
        if (item == NULL || fullListIndex < 0
                || fullListIndex >= FullListCountItems()) {
                return NULL;
        }

        uint32 level = item->OutlineLevel();
        int32 superIndex;
        BListItem* super = _SuperitemForIndex(fullListIndex, level, &superIndex);

        if (item->IsItemVisible()) {
                // remove children, too
                while (fullListIndex + 1 < FullListCountItems()) {
                        BListItem* subItem = FullListItemAt(fullListIndex + 1);

                        if (subItem->OutlineLevel() <= level)
                                break;

                        if (subItem->IsItemVisible())
                                BListView::RemoveItem(subItem);

                        fFullList.RemoveItem(fullListIndex + 1);
                        delete subItem;
                }
                BListView::RemoveItem(item);
        }

        fFullList.RemoveItem(fullListIndex);

        if (super != NULL) {
                // we might need to change the fHasSubitems field of the parent
                BListItem* child = FullListItemAt(superIndex + 1);
                if (child == NULL || child->OutlineLevel() <= super->OutlineLevel())
                        super->fHasSubitems = false;
        }

        return item;
}


/*!     Returns the super item before the item specified by \a fullListIndex
        and \a level.
*/
BListItem*
BOutlineListView::_SuperitemForIndex(int32 fullListIndex, int32 level,
        int32* _superIndex)
{
        BListItem* item;
        fullListIndex--;

        while (fullListIndex >= 0) {
                if ((item = FullListItemAt(fullListIndex))->OutlineLevel()
                                < (uint32)level) {
                        if (_superIndex != NULL)
                                *_superIndex = fullListIndex;
                        return item;
                }

                fullListIndex--;
        }

        return NULL;
}


int32
BOutlineListView::_FindPreviousVisibleIndex(int32 fullListIndex)
{
        fullListIndex--;

        while (fullListIndex >= 0) {
                if (FullListItemAt(fullListIndex)->fVisible)
                        return fullListIndex;

                fullListIndex--;
        }

        return -1;
}


status_t
BOutlineListView::_ItemsUnderSetup(BListItem* superItem, int32& startIndex, uint32& baseLevel) const
{
        if (superItem != NULL) {
                startIndex = FullListIndexOf(superItem) + 1;
                if (startIndex == 0)
                        return B_ENTRY_NOT_FOUND;
                baseLevel = superItem->OutlineLevel() + 1;
        } else {
                startIndex = 0;
                baseLevel = 0;
        }
        return B_OK;
}