/////////////////////////////////////////////////////////////////////////////
// Name:        src/generic/treectlg.cpp
// Purpose:     generic tree control implementation
// Author:      Robert Roebling
// Created:     01/02/97
// Modified:    22/10/98 - almost total rewrite, simpler interface (VZ)
// Copyright:   (c) 1998 Robert Roebling and Julian Smart
// Licence:     wxWindows licence
/////////////////////////////////////////////////////////////////////////////

// =============================================================================
// declarations
// =============================================================================

// -----------------------------------------------------------------------------
// headers
// -----------------------------------------------------------------------------

// For compilers that support precompilation, includes "wx.h".
#include "wx/wxprec.h"


#if wxUSE_TREECTRL

#include "wx/treectrl.h"

#ifndef WX_PRECOMP
    #include "wx/dcclient.h"
    #include "wx/timer.h"
    #include "wx/settings.h"
    #include "wx/listbox.h"
    #include "wx/textctrl.h"
#endif

#include "wx/generic/treectlg.h"
#include "wx/imaglist.h"
#include "wx/itemattr.h"

#include "wx/renderer.h"

#include "wx/generic/private/drawbitmap.h"

#ifdef __WXMAC__
    #include "wx/osx/private.h"
#endif

// -----------------------------------------------------------------------------
// array types
// -----------------------------------------------------------------------------

class wxGenericTreeItem;

using wxGenericTreeItems = std::vector<wxGenericTreeItem*>;

// ----------------------------------------------------------------------------
// constants
// ----------------------------------------------------------------------------

static const int NO_IMAGE = -1;

static const int PIXELS_PER_UNIT = 10;

// the margin between the item state image and the item normal image
static const int MARGIN_BETWEEN_STATE_AND_IMAGE = 2;

// the margin between the item image and the item text
static const int MARGIN_BETWEEN_IMAGE_AND_TEXT = 4;

// -----------------------------------------------------------------------------
// private classes
// -----------------------------------------------------------------------------

// timer used for enabling in-place edit
class wxTreeRenameTimer: public wxTimer
{
public:
    // start editing the current item after half a second (if the mouse hasn't
    // been clicked/moved)
    enum { DELAY = 500 };

    wxTreeRenameTimer( wxGenericTreeCtrl *owner );

    virtual void Notify() override;

private:
    wxGenericTreeCtrl *m_owner;

    wxDECLARE_NO_COPY_CLASS(wxTreeRenameTimer);
};

// control used for in-place edit
class wxTreeTextCtrl: public wxTextCtrl
{
public:
    wxTreeTextCtrl(wxGenericTreeCtrl *owner, wxGenericTreeItem *item);

    void EndEdit( bool discardChanges );

    const wxGenericTreeItem* item() const { return m_itemEdited; }

protected:
    void OnChar( wxKeyEvent &event );
    void OnKillFocus( wxFocusEvent &event );

    void IncreaseSizeForText( const wxString& text );

    bool AcceptChanges();
    void Finish( bool setfocus );

private:
    wxGenericTreeCtrl  *m_owner;
    wxGenericTreeItem  *m_itemEdited;
    wxString            m_startValue;
    bool                m_aboutToFinish;

    wxDECLARE_EVENT_TABLE();
    wxDECLARE_NO_COPY_CLASS(wxTreeTextCtrl);
};

// timer used to clear wxGenericTreeCtrl::m_findPrefix if no key was pressed
// for a sufficiently long time
class wxTreeFindTimer : public wxTimer
{
public:
    // reset the current prefix after half a second of inactivity
    enum { DELAY = 500 };

    wxTreeFindTimer( wxGenericTreeCtrl *owner ) { m_owner = owner; }

    virtual void Notify() override { m_owner->ResetFindState(); }

private:
    wxGenericTreeCtrl *m_owner;

    wxDECLARE_NO_COPY_CLASS(wxTreeFindTimer);
};

// a tree item
class wxGenericTreeItem
{
public:
    // ctors & dtor
    wxGenericTreeItem()
    {
        m_data = nullptr;
        m_widthText =
        m_heightText = -1;
    }

    wxGenericTreeItem( wxGenericTreeItem *parent,
                       const wxString& text,
                       int image,
                       int selImage,
                       wxTreeItemData *data );

    ~wxGenericTreeItem();

    // trivial accessors
    wxGenericTreeItems& GetChildren() { return m_children; }

    const wxString& GetText() const { return m_text; }
    int GetImage(wxTreeItemIcon which = wxTreeItemIcon_Normal) const
        { return m_images[which]; }
    wxTreeItemData *GetData() const { return m_data; }
    int GetState() const { return m_state; }

    // returns the current image for the item (depending on its
    // selected/expanded/whatever state)
    int GetCurrentImage() const;

    void SetText(const wxString& text)
    {
        m_text = text;

        ResetTextSize();
    }

    void SetImage(int image, wxTreeItemIcon which)
    {
        m_images[which] = image;
        m_width = 0;
    }

    void SetData(wxTreeItemData *data) { m_data = data; }
    void SetState(int state) { m_state = state; m_width = 0; }

    void SetHasPlus(bool has = true) { m_hasPlus = has; }

    void SetBold(bool bold)
    {
        m_isBold = bold;

        ResetTextSize();
    }

    int GetX() const { return m_x; }
    int GetY() const { return m_y; }

    void SetX(int x) { m_x = x; }
    void SetY(int y) { m_y = y; }

    int GetHeight() const { return m_height; }
    int GetWidth() const { return m_width; }

    int GetTextHeight() const
    {
        wxASSERT_MSG( m_heightText != -1, "must call CalculateSize() first" );

        return m_heightText;
    }

    int GetTextWidth() const
    {
        wxASSERT_MSG( m_widthText != -1, "must call CalculateSize() first" );

        return m_widthText;
    }

    wxGenericTreeItem *GetParent() const { return m_parent; }

    // sets the items font for the specified DC if it uses any special font or
    // simply returns false otherwise
    bool SetFont(wxGenericTreeCtrl *control, wxReadOnlyDC& dc) const
    {
        wxFont font;

        wxItemAttr * const attr = GetAttributes();
        if ( attr && attr->HasFont() )
            font = attr->GetFont();
        else if ( IsBold() )
            font = control->m_boldFont;
        else
            return false;

        dc.SetFont(font);
        return true;
    }

    // operations

    // deletes all children notifying the treectrl about it
    void DeleteChildren(wxGenericTreeCtrl *tree);

    // get count of all children (and grand children if 'recursively')
    size_t GetChildrenCount(bool recursively = true) const;

    void Insert(wxGenericTreeItem *child, size_t index)
        { m_children.insert(m_children.begin() + index, child); }

    // calculate and cache the item size using either the provided DC (which is
    // supposed to already have wxGenericTreeCtrl font selected into it!) or a
    // wxInfoDC associated with the control
    void CalculateSize(wxGenericTreeCtrl *control, wxReadOnlyDC& dc)
        { DoCalculateSize(control, dc); }
    void CalculateSize(wxGenericTreeCtrl *control);

    void GetSize( int &x, int &y, const wxGenericTreeCtrl* );

    void ResetSize() { m_width = 0; }
    void ResetTextSize() { m_width = 0; m_widthText = -1; }
    void RecursiveResetSize();
    void RecursiveResetTextSize();

        // return the item at given position (or nullptr if no item), onButton is
        // true if the point belongs to the item's button, otherwise it lies
        // on the item's label
    wxGenericTreeItem *HitTest( const wxPoint& point,
                                const wxGenericTreeCtrl *,
                                int &flags,
                                int level );

    void Expand() { m_isCollapsed = false; }
    void Collapse() { m_isCollapsed = true; }

    void SetHilight( bool set = true ) { m_hasHilight = set; }

    // status inquiries
    bool HasChildren() const { return !m_children.empty(); }
    bool IsSelected()  const { return m_hasHilight != 0; }
    bool IsExpanded()  const { return !m_isCollapsed; }
    bool HasPlus()     const { return m_hasPlus || HasChildren(); }
    bool IsBold()      const { return m_isBold != 0; }

    // attributes
        // get them - may be null
    wxItemAttr *GetAttributes() const { return m_attr; }
        // get them ensuring that the pointer is not null
    wxItemAttr& Attr()
    {
        if ( !m_attr )
        {
            m_attr = new wxItemAttr;
            m_ownsAttr = true;
        }
        return *m_attr;
    }
        // set them
    void SetAttributes(wxItemAttr *attr)
    {
        if ( m_ownsAttr )
            delete m_attr;
        m_attr = attr;
        m_ownsAttr = false;
        m_width = 0;
        m_widthText = -1;
    }
        // set them and delete when done
    void AssignAttributes(wxItemAttr *attr)
    {
        SetAttributes(attr);
        m_ownsAttr = true;
        m_width = 0;
        m_widthText = -1;
    }

private:
    // calculate the size of this item, i.e. set m_width, m_height and
    // m_widthText and m_heightText properly
    void DoCalculateSize(wxGenericTreeCtrl *control, wxReadOnlyDC& dc);

    // since there can be very many of these, we save size by chosing
    // the smallest representation for the elements and by ordering
    // the members to avoid padding.
    wxString            m_text;         // label to be rendered for item
    int                 m_widthText;
    int                 m_heightText;

    wxTreeItemData     *m_data;         // user-provided data

    int                 m_state;        // item state

    wxGenericTreeItems  m_children;     // list of children
    wxGenericTreeItem  *m_parent;       // parent of this item

    wxItemAttr     *m_attr;         // attributes???

    // tree ctrl images for the normal, selected, expanded and
    // expanded+selected states
    int                 m_images[wxTreeItemIcon_Max];

    wxCoord             m_x;            // (virtual) offset from top
    wxCoord             m_y;            // (virtual) offset from left
    int                 m_width;        // width of this item
    int                 m_height;       // height of this item

    // use bitfields to save size
    unsigned int        m_isCollapsed :1;
    unsigned int        m_hasHilight  :1; // same as focused
    unsigned int        m_hasPlus     :1; // used for item which doesn't have
                                          // children but has a [+] button
    unsigned int        m_isBold      :1; // render the label in bold font
    unsigned int        m_ownsAttr    :1; // delete attribute when done

    wxDECLARE_NO_COPY_CLASS(wxGenericTreeItem);
};

// =============================================================================
// implementation
// =============================================================================

// ----------------------------------------------------------------------------
// private functions
// ----------------------------------------------------------------------------

// Get wxGenericTreeItem from wxTreeItemId.
static inline wxGenericTreeItem* GetItemPtr(const wxTreeItemId& item)
{
    return static_cast<wxGenericTreeItem*>(item.GetID());
}

// translate the key or mouse event flags to the type of selection we're
// dealing with
static void EventFlagsToSelType(long style,
                                bool shiftDown,
                                bool ctrlDown,
                                bool &is_multiple,
                                bool &extended_select,
                                bool &unselect_others)
{
    is_multiple = (style & wxTR_MULTIPLE) != 0;
    extended_select = shiftDown && is_multiple;
    unselect_others = !(extended_select || (ctrlDown && is_multiple));
}

// check if the given item is under another one
static bool
IsDescendantOf(const wxGenericTreeItem *parent, const wxGenericTreeItem *item)
{
    while ( item )
    {
        if ( item == parent )
        {
            // item is a descendant of parent
            return true;
        }

        item = item->GetParent();
    }

    return false;
}

static int
FindItemIndex(const wxGenericTreeItems& items, const wxGenericTreeItem* item)
{
    const int count = wxSsize(items);
    for ( int n = 0; n < count; n++ )
    {
        if ( items[n] == item )
            return n;
    }

    return wxNOT_FOUND;
}

// -----------------------------------------------------------------------------
// wxTreeRenameTimer (internal)
// -----------------------------------------------------------------------------

wxTreeRenameTimer::wxTreeRenameTimer( wxGenericTreeCtrl *owner )
{
    m_owner = owner;
}

void wxTreeRenameTimer::Notify()
{
    m_owner->OnRenameTimer();
}

//-----------------------------------------------------------------------------
// wxTreeTextCtrl (internal)
//-----------------------------------------------------------------------------

wxBEGIN_EVENT_TABLE(wxTreeTextCtrl,wxTextCtrl)
    EVT_CHAR           (wxTreeTextCtrl::OnChar)
    EVT_KILL_FOCUS     (wxTreeTextCtrl::OnKillFocus)
wxEND_EVENT_TABLE()

wxTreeTextCtrl::wxTreeTextCtrl(wxGenericTreeCtrl *owner,
                               wxGenericTreeItem *itm)
              : m_itemEdited(itm), m_startValue(itm->GetText())
{
    m_owner = owner;
    m_aboutToFinish = false;

    // Create the text hidden to show it with the correct size -- which we
    // can't determine before creating it.
    Hide();
    Create(m_owner, wxID_ANY, m_startValue);

    wxRect rect;
    m_owner->GetBoundingRect(m_itemEdited, rect, true);

    const wxSize textSize = rect.GetSize();
    wxSize fullSize = GetSizeFromTextSize(textSize);

    // Ensure that the text field covers tree item.
    fullSize.x = wxMax(fullSize.x, textSize.x + 5);

    // Correct position for better appearance.
#ifdef __WXMSW__
    rect.x -= 5;
#else
    rect.x -= (fullSize.x - textSize.x) / 2;
#endif

    if ( fullSize.y > textSize.y )
        rect.y -= (fullSize.y - textSize.y) / 2;

    // Also check that the control fits into the parent window.
    const int totalWidth = m_owner->GetClientSize().x;
    if ( rect.x + fullSize.x > totalWidth )
    {
        fullSize.x = totalWidth - rect.x;
    }

    rect.SetSize(fullSize);

    SetSize(rect);
    Show();

    SelectAll();
}

void wxTreeTextCtrl::EndEdit(bool discardChanges)
{
    if ( m_aboutToFinish )
    {
        // We already called Finish which cannot be called
        // more than once.
        return;
    }

    m_aboutToFinish = true;

    if ( discardChanges )
    {
        m_owner->OnRenameCancelled(m_itemEdited);

        Finish( true );
    }
    else
    {
        // Notify the owner about the changes
        AcceptChanges();

        // Even if vetoed, close the control (consistent with MSW)
        Finish( true );
    }
}

bool wxTreeTextCtrl::AcceptChanges()
{
    const wxString value = GetValue();

    if ( value == m_startValue )
    {
        // nothing changed, always accept
        // when an item remains unchanged, the owner
        // needs to be notified that the user decided
        // not to change the tree item label, and that
        // the edit has been cancelled

        m_owner->OnRenameCancelled(m_itemEdited);
        return true;
    }

    if ( !m_owner->OnRenameAccept(m_itemEdited, value) )
    {
        // vetoed by the user
        return false;
    }

    // accepted, do rename the item
    m_owner->SetItemText(m_itemEdited, value);

    return true;
}

void wxTreeTextCtrl::Finish( bool setfocus )
{
    m_owner->ResetTextControl();

#ifdef __WXMAC__
    // On wxMac, modal event loops avoid deleting pending objects.
    // Hide control so it does not remain visible e.g. if the tree
    // control is used in a dialog.
    Hide();
#endif

    wxPendingDelete.Append(this);

    if (setfocus)
        m_owner->SetFocus();
}

void wxTreeTextCtrl::OnChar( wxKeyEvent &event )
{
    switch ( event.m_keyCode )
    {
        case WXK_RETURN:
            EndEdit( false );
            break;

        case WXK_ESCAPE:
            EndEdit( true );
            break;

        default:
            if ( !m_aboutToFinish )
            {
                wxChar ch = event.GetUnicodeKey();
                if ( ch != WXK_NONE )
                {
                    wxString value = GetValue();

                    long from, to;
                    GetSelection( &from, &to );
                    if ( from != to )
                    {
                        value.Remove( from, to - from );
                    }

                    IncreaseSizeForText( value + ch );
                }
            }
            event.Skip();
    }
}

void wxTreeTextCtrl::IncreaseSizeForText( const wxString& text )
{
    // auto-grow the textctrl:
    wxSize parentSize = m_owner->GetClientSize();
    wxPoint myPos = GetPosition();
    wxSize mySize = GetSize();
    int sx = GetSizeFromText(text).x;
    if (myPos.x + sx > parentSize.x)
        sx = parentSize.x - myPos.x;
    if (sx > mySize.x)
        SetSize(sx, wxDefaultCoord);
}

void wxTreeTextCtrl::OnKillFocus( wxFocusEvent &event )
{
    if ( !m_aboutToFinish )
    {
        m_aboutToFinish = true;
        if ( !AcceptChanges() )
            m_owner->OnRenameCancelled( m_itemEdited );

        Finish( false );
    }

    // We should let the native text control handle focus, too.
    event.Skip();
}

// -----------------------------------------------------------------------------
// wxGenericTreeItem
// -----------------------------------------------------------------------------

wxGenericTreeItem::wxGenericTreeItem(wxGenericTreeItem *parent,
                                     const wxString& text,
                                     int image, int selImage,
                                     wxTreeItemData *data)
                 : m_text(text)
{
    m_images[wxTreeItemIcon_Normal] = image;
    m_images[wxTreeItemIcon_Selected] = selImage;
    m_images[wxTreeItemIcon_Expanded] = NO_IMAGE;
    m_images[wxTreeItemIcon_SelectedExpanded] = NO_IMAGE;

    m_data = data;
    m_state = wxTREE_ITEMSTATE_NONE;
    m_x = m_y = 0;

    m_isCollapsed = true;
    m_hasHilight = false;
    m_hasPlus = false;
    m_isBold = false;

    m_parent = parent;

    m_attr = nullptr;
    m_ownsAttr = false;

    // We don't know the height here yet.
    m_width = 0;
    m_height = 0;

    m_widthText = -1;
    m_heightText = -1;
}

wxGenericTreeItem::~wxGenericTreeItem()
{
    delete m_data;

    if (m_ownsAttr)
        delete m_attr;

    wxASSERT_MSG( m_children.empty(),
                  "must call DeleteChildren() before deleting the item" );
}

void wxGenericTreeItem::DeleteChildren(wxGenericTreeCtrl *tree)
{
    size_t count = m_children.size();
    for ( size_t n = 0; n < count; n++ )
    {
        wxGenericTreeItem *child = m_children[n];
        tree->SendDeleteEvent(child);

        child->DeleteChildren(tree);
        if ( child == tree->m_select_me )
            tree->m_select_me = nullptr;
        delete child;
    }

    m_children.clear();
}

size_t wxGenericTreeItem::GetChildrenCount(bool recursively) const
{
    size_t count = m_children.size();
    if ( !recursively )
        return count;

    size_t total = count;
    for (size_t n = 0; n < count; ++n)
    {
        total += m_children[n]->GetChildrenCount();
    }

    return total;
}

void wxGenericTreeItem::GetSize( int &x, int &y,
                                 const wxGenericTreeCtrl *theButton )
{
    int bottomY=m_y+theButton->GetLineHeight(this);
    if ( y < bottomY )
        y = bottomY;
    int width = m_x +  m_width;
    if ( x < width )
        x = width;

    if (IsExpanded())
    {
        size_t count = m_children.size();
        for ( size_t n = 0; n < count; ++n )
        {
            m_children[n]->GetSize( x, y, theButton );
        }
    }
}

wxGenericTreeItem *wxGenericTreeItem::HitTest(const wxPoint& point,
                                              const wxGenericTreeCtrl *theCtrl,
                                              int &flags,
                                              int level)
{
    // for a hidden root node, don't evaluate it, but do evaluate children
    if ( !(level == 0 && theCtrl->HasFlag(wxTR_HIDE_ROOT)) )
    {
        // evaluate the item
        int h = theCtrl->GetLineHeight(this);
        if ((point.y > m_y) && (point.y < m_y + h))
        {
            int y_mid = m_y + h/2;
            if (point.y < y_mid )
                flags |= wxTREE_HITTEST_ONITEMUPPERPART;
            else
                flags |= wxTREE_HITTEST_ONITEMLOWERPART;

            int xCross = m_x - theCtrl->FromDIP(theCtrl->GetSpacing());
#if defined(__WXMAC__) || defined(__WXGTK__)
            // according to the drawing code the triangles are drawn
            // at -4/-4  from the position up to +10/+10 max, but
            // we have to detect the clicks at -10,-10 as also the
            // native controls react to mouse click on the full
            // height of the entry, not just where the triangle or
            // chevron is drawn
            const int triangleStart = theCtrl->FromDIP(10); // -10,-10
            const int triangleEnd = theCtrl->FromDIP(10);   // +10, +10
            if ((point.x > xCross - triangleStart) && (point.x < xCross + triangleEnd) &&
                (point.y > y_mid - triangleStart) && (point.y < y_mid + triangleEnd) &&
                HasPlus() && theCtrl->HasButtons() )
#else
            // 5 is the size of the plus sign
            const int plusSize = 1 + theCtrl->FromDIP(5);
            if ((point.x > xCross - plusSize) && (point.x < xCross + plusSize) &&
                (point.y > y_mid - plusSize) && (point.y < y_mid + plusSize) &&
                HasPlus() && theCtrl->HasButtons() )
#endif
            {
                flags |= wxTREE_HITTEST_ONITEMBUTTON;
                return this;
            }

            if ((point.x >= m_x) && (point.x <= m_x+m_width))
            {
                int image_w = -1;

                // assuming every image (normal and selected) has the same size!
                if ( (GetImage() != NO_IMAGE) && theCtrl->HasImages() )
                {
                    image_w = theCtrl->GetImageLogicalSize(theCtrl).x;
                }

                int state_w = -1;

                if ( (GetState() != wxTREE_ITEMSTATE_NONE) &&
                        theCtrl->m_imagesState.HasImages() )
                {
                    int state_h;
                    theCtrl->m_imagesState.GetImageLogicalSize(theCtrl,
                                                       state_w, state_h);
                }

                if ((state_w != -1) && (point.x <= m_x + state_w + 1))
                    flags |= wxTREE_HITTEST_ONITEMSTATEICON;
                else if ((image_w != -1) &&
                         (point.x <= m_x +
                            (state_w != -1 ? state_w +
                                                MARGIN_BETWEEN_STATE_AND_IMAGE
                                           : 0)
                                            + image_w + 1))
                    flags |= wxTREE_HITTEST_ONITEMICON;
                else
                    flags |= wxTREE_HITTEST_ONITEMLABEL;

                return this;
            }

            if (point.x < m_x)
                flags |= wxTREE_HITTEST_ONITEMINDENT;
            if (point.x > m_x+m_width)
                flags |= wxTREE_HITTEST_ONITEMRIGHT;

            return this;
        }

        // if children are expanded, fall through to evaluate them
        if (m_isCollapsed)
            return nullptr;
    }

    // evaluate children
    size_t count = m_children.size();
    for ( size_t n = 0; n < count; n++ )
    {
        wxGenericTreeItem *res = m_children[n]->HitTest( point,
                                                         theCtrl,
                                                         flags,
                                                         level + 1 );
        if ( res != nullptr )
            return res;
    }

    return nullptr;
}

int wxGenericTreeItem::GetCurrentImage() const
{
    int image = NO_IMAGE;
    if ( IsExpanded() )
    {
        if ( IsSelected() )
        {
            image = GetImage(wxTreeItemIcon_SelectedExpanded);
        }

        if ( image == NO_IMAGE )
        {
            // we usually fall back to the normal item, but try just the
            // expanded one (and not selected) first in this case
            image = GetImage(wxTreeItemIcon_Expanded);
        }
    }
    else // not expanded
    {
        if ( IsSelected() )
            image = GetImage(wxTreeItemIcon_Selected);
    }

    // maybe it doesn't have the specific image we want,
    // try the default one instead
    if ( image == NO_IMAGE )
        image = GetImage();

    return image;
}

void wxGenericTreeItem::CalculateSize(wxGenericTreeCtrl* control)
{
    // check if we need to do anything before creating the DC
    if ( m_width != 0 )
        return;

    wxInfoDC dc(control);
    DoCalculateSize(control, dc);
}

void
wxGenericTreeItem::DoCalculateSize(wxGenericTreeCtrl* control,
                                   wxReadOnlyDC& dc)
{
    if ( m_width != 0 ) // Size known, nothing to do
        return;

    if ( m_widthText == -1 )
    {
        bool fontChanged = false;
        if ( SetFont(control, dc) )
        {
            fontChanged = true;
        }

        dc.GetTextExtent( GetText(), &m_widthText, &m_heightText );

        // restore normal font if the DC used it previously and we changed it
        if ( fontChanged )
             dc.SetFont(control->GetFont());
    }

    int text_h = m_heightText + 2;

    int image_h = 0, image_w = 0;
    if ( GetCurrentImage() != NO_IMAGE && control->HasImages() )
    {
        const wxSize imageSize = control->GetImageLogicalSize(control);
        image_h = imageSize.y;
        image_w = imageSize.x + MARGIN_BETWEEN_IMAGE_AND_TEXT;
    }

    int state_h = 0, state_w = 0;
    int state = GetState();
    if ( state != wxTREE_ITEMSTATE_NONE && control->m_imagesState.HasImages() )
    {
        control->m_imagesState.GetImageLogicalSize(control, state_w, state_h);
        if ( image_w != 0 )
            state_w += MARGIN_BETWEEN_STATE_AND_IMAGE;
        else
            state_w += MARGIN_BETWEEN_IMAGE_AND_TEXT;
    }

    int img_h = wxMax(state_h, image_h);
    m_height = wxMax(img_h, text_h);

    m_height += control->FromDIP(2); // See CalculateLineHeight().

    if (m_height > control->m_lineHeight)
        control->m_lineHeight = m_height;

    m_width = state_w + image_w + m_widthText + 2;
}

void wxGenericTreeItem::RecursiveResetSize()
{
    m_width = 0;

    const size_t count = m_children.size();
    for (size_t i = 0; i < count; i++ )
        m_children[i]->RecursiveResetSize();
}

void wxGenericTreeItem::RecursiveResetTextSize()
{
    m_width = 0;
    m_widthText = -1;

    const size_t count = m_children.size();
    for (size_t i = 0; i < count; i++ )
        m_children[i]->RecursiveResetTextSize();
}

// -----------------------------------------------------------------------------
// wxGenericTreeCtrl implementation
// -----------------------------------------------------------------------------

wxIMPLEMENT_DYNAMIC_CLASS(wxGenericTreeCtrl, wxControl);

wxBEGIN_EVENT_TABLE(wxGenericTreeCtrl, wxTreeCtrlBase)
    EVT_PAINT          (wxGenericTreeCtrl::OnPaint)
    EVT_SIZE           (wxGenericTreeCtrl::OnSize)
    EVT_MOUSE_EVENTS   (wxGenericTreeCtrl::OnMouse)
    EVT_KEY_DOWN       (wxGenericTreeCtrl::OnKeyDown)
    EVT_CHAR           (wxGenericTreeCtrl::OnChar)
    EVT_SET_FOCUS      (wxGenericTreeCtrl::OnSetFocus)
    EVT_KILL_FOCUS     (wxGenericTreeCtrl::OnKillFocus)
    EVT_TREE_ITEM_GETTOOLTIP(wxID_ANY, wxGenericTreeCtrl::OnGetToolTip)
    EVT_SYS_COLOUR_CHANGED(wxGenericTreeCtrl::OnSysColourChanged)
wxEND_EVENT_TABLE()

// -----------------------------------------------------------------------------
// construction/destruction
// -----------------------------------------------------------------------------

void wxGenericTreeCtrl::Init()
{
    m_current =
    m_key_current =
    m_anchor =
    m_select_me = nullptr;
    m_hasFocus = false;
    m_dirty = false;

    m_lineHeight = 10;
    m_indent = 0;
    m_spacing = 0;

    m_dragCount = 0;
    m_isDragging = false;
    m_dropTarget = m_oldSelection = nullptr;
    m_underMouse = nullptr;
    m_textCtrl = nullptr;

    m_renameTimer = nullptr;

    m_findTimer = nullptr;
    m_findBell = 0;  // default is to not ring bell at all

    m_dropEffectAboveItem = false;

    m_dndEffect = NoEffect;
    m_dndEffectItem = nullptr;

    m_lastOnSame = false;
}

bool wxGenericTreeCtrl::Create(wxWindow *parent,
                               wxWindowID id,
                               const wxPoint& pos,
                               const wxSize& size,
                               long style,
                               const wxValidator& validator,
                               const wxString& name )
{
    if ( !wxControl::Create( parent, id, pos, size,
                             style|wxHSCROLL|wxVSCROLL|wxWANTS_CHARS,
                             validator,
                             name ) )
        return false;

    m_hasExplicitFgCol = m_hasFgCol;
    m_hasExplicitBgCol = m_hasBgCol;
    m_hasExplicitFont = m_hasFont;

    InitVisualAttributes();

    SetInitialSize(size);

    return true;
}

wxGenericTreeCtrl::~wxGenericTreeCtrl()
{
    DeleteAllItems();

    delete m_renameTimer;
    delete m_findTimer;
}

void wxGenericTreeCtrl::EnableBellOnNoMatch( bool on )
{
    m_findBell = on;
}

void wxGenericTreeCtrl::InitVisualAttributes()
{
    // We want to use the default system colours/fonts here unless the user
    // explicitly configured something different. We also need to reset the
    // m_hasExplicitXXX variables to false to prevent them from being left set
    // to "true" after calling the corresponding SetXXX(), as otherwise we
    // wouldn't update the colours/fonts the next time the system colours
    // change.
    const wxVisualAttributes attr(GetDefaultAttributes());
    if ( !m_hasExplicitFgCol )
    {
        SetOwnForegroundColour(attr.colFg);
        m_hasExplicitFgCol = false;
    }

    if ( !m_hasExplicitBgCol )
    {
        SetOwnBackgroundColour(attr.colBg);
        m_hasExplicitBgCol = false;
    }

    if ( !m_hasExplicitFont )
    {
        SetOwnFont(attr.font);
        m_hasExplicitFont = false;
    }


    m_hilightBrush = wxBrush(wxSystemSettings::GetColour(wxSYS_COLOUR_HIGHLIGHT));
    m_hilightUnfocusedBrush = wxBrush(wxSystemSettings::GetColour(wxSYS_COLOUR_BTNSHADOW));

    m_dottedPen = wxPen(wxSystemSettings::GetColour(wxSYS_COLOUR_GRAYTEXT), 1, wxPENSTYLE_DOT);

    m_boldFont = m_font.Bold();

    m_indent = 10;
    m_spacing = 10;
}

// -----------------------------------------------------------------------------
// accessors
// -----------------------------------------------------------------------------

unsigned int wxGenericTreeCtrl::GetCount() const
{
    if ( !m_anchor )
    {
        // the tree is empty
        return 0;
    }

    unsigned int count = m_anchor->GetChildrenCount();
    if ( !HasFlag(wxTR_HIDE_ROOT) )
    {
        // take the root itself into account
        count++;
    }

    return count;
}

void wxGenericTreeCtrl::SetIndent(unsigned int indent)
{
    m_indent = indent;
    m_dirty = true;
}

size_t
wxGenericTreeCtrl::GetChildrenCount(const wxTreeItemId& item,
                                    bool recursively) const
{
    wxCHECK_MSG( item.IsOk(), 0u, wxT("invalid tree item") );

    return GetItemPtr(item)->GetChildrenCount(recursively);
}

void wxGenericTreeCtrl::SetWindowStyleFlag(long styles)
{
    // Do not try to expand the root node if it hasn't been created yet
    if (m_anchor && !HasFlag(wxTR_HIDE_ROOT) && (styles & wxTR_HIDE_ROOT))
    {
        // if we will hide the root, make sure children are visible
        m_anchor->SetHasPlus();
        m_anchor->Expand();
        CalculatePositions();
    }

    // right now, just sets the styles.  Eventually, we may
    // want to update the inherited styles, but right now
    // none of the parents has updatable styles
    m_windowStyle = styles;
    m_dirty = true;
}

// -----------------------------------------------------------------------------
// functions to work with tree items
// -----------------------------------------------------------------------------

wxString wxGenericTreeCtrl::GetItemText(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), wxEmptyString, wxT("invalid tree item") );

    return GetItemPtr(item)->GetText();
}

int wxGenericTreeCtrl::GetItemImage(const wxTreeItemId& item,
                             wxTreeItemIcon which) const
{
    wxCHECK_MSG( item.IsOk(), -1, wxT("invalid tree item") );

    return GetItemPtr(item)->GetImage(which);
}

wxTreeItemData *wxGenericTreeCtrl::GetItemData(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), nullptr, wxT("invalid tree item") );

    return GetItemPtr(item)->GetData();
}

int wxGenericTreeCtrl::DoGetItemState(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), wxTREE_ITEMSTATE_NONE, wxT("invalid tree item") );

    wxGenericTreeItem *pItem = GetItemPtr(item);
    return pItem->GetState();
}

wxColour wxGenericTreeCtrl::GetItemTextColour(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), wxNullColour, wxT("invalid tree item") );

    wxGenericTreeItem *pItem = GetItemPtr(item);
    return pItem->Attr().GetTextColour();
}

wxColour
wxGenericTreeCtrl::GetItemBackgroundColour(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), wxNullColour, wxT("invalid tree item") );

    wxGenericTreeItem *pItem = GetItemPtr(item);
    return pItem->Attr().GetBackgroundColour();
}

wxFont wxGenericTreeCtrl::GetItemFont(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), wxNullFont, wxT("invalid tree item") );

    wxGenericTreeItem *pItem = GetItemPtr(item);
    return pItem->Attr().GetFont();
}

void
wxGenericTreeCtrl::SetItemText(const wxTreeItemId& item, const wxString& text)
{
    wxCHECK_RET( item.IsOk(), wxT("invalid tree item") );

    wxGenericTreeItem *pItem = GetItemPtr(item);
    pItem->SetText(text);
    pItem->CalculateSize(this);
    RefreshLine(pItem);
}

void wxGenericTreeCtrl::SetItemImage(const wxTreeItemId& item,
                              int image,
                              wxTreeItemIcon which)
{
    wxCHECK_RET( item.IsOk(), wxT("invalid tree item") );

    wxGenericTreeItem *pItem = GetItemPtr(item);
    pItem->SetImage(image, which);
    pItem->CalculateSize(this);
    RefreshLine(pItem);
}

void
wxGenericTreeCtrl::SetItemData(const wxTreeItemId& item, wxTreeItemData *data)
{
    wxCHECK_RET( item.IsOk(), wxT("invalid tree item") );

    if (data)
        data->SetId( item );

    GetItemPtr(item)->SetData(data);
}

void wxGenericTreeCtrl::DoSetItemState(const wxTreeItemId& item, int state)
{
    wxCHECK_RET( item.IsOk(), wxT("invalid tree item") );

    wxGenericTreeItem *pItem = GetItemPtr(item);
    pItem->SetState(state);
    pItem->CalculateSize(this);
    RefreshLine(pItem);
}

void wxGenericTreeCtrl::SetItemHasChildren(const wxTreeItemId& item, bool has)
{
    wxCHECK_RET( item.IsOk(), wxT("invalid tree item") );

    wxGenericTreeItem *pItem = GetItemPtr(item);
    pItem->SetHasPlus(has);
    RefreshLine(pItem);
}

void wxGenericTreeCtrl::SetItemBold(const wxTreeItemId& item, bool bold)
{
    wxCHECK_RET( item.IsOk(), wxT("invalid tree item") );

    // avoid redrawing the tree if no real change
    wxGenericTreeItem *pItem = GetItemPtr(item);
    if ( pItem->IsBold() != bold )
    {
        pItem->SetBold(bold);

        // recalculate the item size as bold and non bold fonts have different
        // widths
        pItem->CalculateSize(this);
        RefreshLine(pItem);
    }
}

void wxGenericTreeCtrl::SetItemDropHighlight(const wxTreeItemId& item,
                                             bool highlight)
{
    wxCHECK_RET( item.IsOk(), wxT("invalid tree item") );

    wxColour fg, bg;

    if (highlight)
    {
        bg = wxSystemSettings::GetColour(wxSYS_COLOUR_HIGHLIGHT);
        fg = wxSystemSettings::GetColour(wxSYS_COLOUR_HIGHLIGHTTEXT);
    }

    wxGenericTreeItem *pItem = GetItemPtr(item);
    pItem->Attr().SetTextColour(fg);
    pItem->Attr().SetBackgroundColour(bg);
    RefreshLine(pItem);
}

void wxGenericTreeCtrl::SetItemTextColour(const wxTreeItemId& item,
                                   const wxColour& col)
{
    wxCHECK_RET( item.IsOk(), wxT("invalid tree item") );

    wxGenericTreeItem *pItem = GetItemPtr(item);
    pItem->Attr().SetTextColour(col);
    RefreshLine(pItem);
}

void wxGenericTreeCtrl::SetItemBackgroundColour(const wxTreeItemId& item,
                                         const wxColour& col)
{
    wxCHECK_RET( item.IsOk(), wxT("invalid tree item") );

    wxGenericTreeItem *pItem = GetItemPtr(item);
    pItem->Attr().SetBackgroundColour(col);
    RefreshLine(pItem);
}

void
wxGenericTreeCtrl::SetItemFont(const wxTreeItemId& item, const wxFont& font)
{
    wxCHECK_RET( item.IsOk(), wxT("invalid tree item") );

    wxGenericTreeItem *pItem = GetItemPtr(item);
    pItem->Attr().SetFont(font);
    pItem->ResetTextSize();
    pItem->CalculateSize(this);
    RefreshLine(pItem);
}

bool wxGenericTreeCtrl::SetFont( const wxFont &font )
{
    if ( !wxTreeCtrlBase::SetFont(font) )
        return false;

    m_hasExplicitFont = true;

    m_boldFont = m_font.Bold();

    CalculateLineHeight();

    if (m_anchor)
        m_anchor->RecursiveResetTextSize();

    return true;
}


// -----------------------------------------------------------------------------
// item status inquiries
// -----------------------------------------------------------------------------

bool wxGenericTreeCtrl::IsVisible(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), false, wxT("invalid tree item") );

    // Hidden root item is never visible.
    if ( item == GetRootItem() && HasFlag(wxTR_HIDE_ROOT) )
        return false;

    // An item is only visible if it's not a descendant of a collapsed item
    wxGenericTreeItem *pItem = GetItemPtr(item);
    wxGenericTreeItem* parent = pItem->GetParent();
    while (parent)
    {
        if (!parent->IsExpanded())
            return false;
        parent = parent->GetParent();
    }

    int startX, startY;
    GetViewStart(& startX, & startY);

    wxSize clientSize = GetClientSize();

    wxRect rect;
    if (!GetBoundingRect(item, rect))
        return false;
    if (rect.GetWidth() == 0 || rect.GetHeight() == 0)
        return false;
    if (rect.GetBottom() < 0 || rect.GetTop() > clientSize.y)
        return false;
    if (rect.GetRight() < 0 || rect.GetLeft() > clientSize.x)
        return false;

    return true;
}

bool wxGenericTreeCtrl::ItemHasChildren(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), false, wxT("invalid tree item") );

    // consider that the item does have children if it has the "+" button: it
    // might not have them (if it had never been expanded yet) but then it
    // could have them as well and it's better to err on this side rather than
    // disabling some operations which are restricted to the items with
    // children for an item which does have them
    return GetItemPtr(item)->HasPlus();
}

bool wxGenericTreeCtrl::IsExpanded(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), false, wxT("invalid tree item") );

    return GetItemPtr(item)->IsExpanded();
}

bool wxGenericTreeCtrl::IsSelected(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), false, wxT("invalid tree item") );

    return GetItemPtr(item)->IsSelected();
}

bool wxGenericTreeCtrl::IsBold(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), false, wxT("invalid tree item") );

    return GetItemPtr(item)->IsBold();
}

// -----------------------------------------------------------------------------
// navigation
// -----------------------------------------------------------------------------

wxTreeItemId wxGenericTreeCtrl::GetItemParent(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), wxTreeItemId(), wxT("invalid tree item") );

    return GetItemPtr(item)->GetParent();
}

wxTreeItemId wxGenericTreeCtrl::GetFirstChild(const wxTreeItemId& item,
                                              wxTreeItemIdValue& cookie) const
{
    wxCHECK_MSG( item.IsOk(), wxTreeItemId(), wxT("invalid tree item") );

    cookie = nullptr;
    return GetNextChild(item, cookie);
}

wxTreeItemId wxGenericTreeCtrl::GetNextChild(const wxTreeItemId& item,
                                             wxTreeItemIdValue& cookie) const
{
    wxCHECK_MSG( item.IsOk(), wxTreeItemId(), wxT("invalid tree item") );

    wxGenericTreeItems& children = GetItemPtr(item)->GetChildren();

    // it's ok to cast cookie to size_t, we never have indices big enough to
    // overflow "void *"
    size_t *pIndex = (size_t *)&cookie;
    if ( *pIndex < children.size() )
    {
        return children[(*pIndex)++];
    }
    else
    {
        // there are no more of them
        return wxTreeItemId();
    }
}

wxTreeItemId wxGenericTreeCtrl::GetLastChild(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), wxTreeItemId(), wxT("invalid tree item") );

    wxGenericTreeItems& children = GetItemPtr(item)->GetChildren();
    return children.empty() ? wxTreeItemId() : wxTreeItemId(children.back());
}

wxTreeItemId wxGenericTreeCtrl::GetNextSibling(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), wxTreeItemId(), wxT("invalid tree item") );

    wxGenericTreeItem *i = GetItemPtr(item);
    wxGenericTreeItem *parent = i->GetParent();
    if ( parent == nullptr )
    {
        // root item doesn't have any siblings
        return wxTreeItemId();
    }

    wxGenericTreeItems& siblings = parent->GetChildren();
    const int index = FindItemIndex(siblings, i);
    wxASSERT( index != wxNOT_FOUND ); // I'm not a child of my parent?

    size_t n = (size_t)(index + 1);
    return n == siblings.size() ? wxTreeItemId()
                                : wxTreeItemId(siblings[n]);
}

wxTreeItemId wxGenericTreeCtrl::GetPrevSibling(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), wxTreeItemId(), wxT("invalid tree item") );

    wxGenericTreeItem *i = GetItemPtr(item);
    wxGenericTreeItem *parent = i->GetParent();
    if ( parent == nullptr )
    {
        // root item doesn't have any siblings
        return wxTreeItemId();
    }

    wxGenericTreeItems& siblings = parent->GetChildren();
    const int index = FindItemIndex(siblings, i);
    wxASSERT( index != wxNOT_FOUND ); // I'm not a child of my parent?

    return index == 0 ? wxTreeItemId()
                      : wxTreeItemId(siblings[(size_t)(index - 1)]);
}

// Only for internal use right now, but should probably be public
wxTreeItemId wxGenericTreeCtrl::GetNext(const wxTreeItemId& item) const
{
    return DoGetNext(item, Next_Any);
}

wxTreeItemId
wxGenericTreeCtrl::DoGetNext(const wxTreeItemId& item, int flags) const
{
    wxCHECK_MSG( item.IsOk(), wxTreeItemId(), wxT("invalid tree item") );

    wxGenericTreeItem *i = GetItemPtr(item);

    // First see if there are any children.
    if ( !(flags & Next_Visible) || i->IsExpanded() )
    {
        wxGenericTreeItems& children = i->GetChildren();
        if (!children.empty())
        {
             return children.front();
        }
    }

     // Try a sibling of this or ancestor instead
     wxTreeItemId p = item;
     wxTreeItemId toFind;
     do
     {
          toFind = GetNextSibling(p);
          p = GetItemParent(p);
     } while (p.IsOk() && !toFind.IsOk());
     return toFind;
}

wxTreeItemId wxGenericTreeCtrl::GetFirstVisibleItem() const
{
    wxTreeItemId itemid = GetRootItem();
    if (!itemid.IsOk())
        return itemid;

    do
    {
        if (IsVisible(itemid))
              return itemid;
        itemid = GetNext(itemid);
    } while (itemid.IsOk());

    return wxTreeItemId();
}

wxTreeItemId wxGenericTreeCtrl::GetNextVisible(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), wxTreeItemId(), wxT("invalid tree item") );
    wxASSERT_MSG( IsVisible(item), wxT("this item itself should be visible") );

    return DoGetNext(item, Next_Visible);
}

wxTreeItemId wxGenericTreeCtrl::GetPrevVisible(const wxTreeItemId& item) const
{
    wxCHECK_MSG( item.IsOk(), wxTreeItemId(), wxT("invalid tree item") );
    wxASSERT_MSG( IsVisible(item), wxT("this item itself should be visible") );

    // find out the starting point
    wxTreeItemId prevItem = GetPrevSibling(item);
    if ( !prevItem.IsOk() )
    {
        prevItem = GetItemParent(item);
    }

    // find the first visible item after it
    while ( prevItem.IsOk() && !IsVisible(prevItem) )
    {
        prevItem = GetNext(prevItem);
        if ( !prevItem.IsOk() || prevItem == item )
        {
            // there are no visible items before item
            return wxTreeItemId();
        }
    }

    // from there we must be able to navigate until this item
    while ( prevItem.IsOk() )
    {
        const wxTreeItemId nextItem = GetNextVisible(prevItem);
        if ( !nextItem.IsOk() || nextItem == item )
            break;

        prevItem = nextItem;
    }

    return prevItem;
}

// called by wxTextTreeCtrl when it marks itself for deletion
void wxGenericTreeCtrl::ResetTextControl()
{
    m_textCtrl = nullptr;
}

void wxGenericTreeCtrl::ResetFindState()
{
    m_findPrefix.clear();
    if ( m_findBell == -1 )
        m_findBell = 1;
}

// find the first item starting with the given prefix after the given item
wxTreeItemId wxGenericTreeCtrl::FindItem(const wxTreeItemId& idParent,
                                         const wxString& prefixOrig) const
{
    // match is case insensitive as this is more convenient to the user: having
    // to press Shift-letter to go to the item starting with a capital letter
    // would be too bothersome
    wxString prefix = prefixOrig.Lower();

    // determine the starting point: we shouldn't take the current item (this
    // allows to switch between two items starting with the same letter just by
    // pressing it) but we shouldn't jump to the next one if the user is
    // continuing to type as otherwise he might easily skip the item he wanted
    wxTreeItemId itemid = idParent;
    if ( prefix.length() == 1 )
    {
        itemid = DoGetNext(itemid, Next_Visible);
    }

    // look for the item starting with the given prefix after it
    while ( itemid.IsOk() && !GetItemText(itemid).Lower().StartsWith(prefix) )
    {
        itemid = DoGetNext(itemid, Next_Visible);
    }

    // if we haven't found anything...
    if ( !itemid.IsOk() )
    {
        // ... wrap to the beginning
        itemid = GetRootItem();
        if ( HasFlag(wxTR_HIDE_ROOT) )
        {
            // can't select virtual root
            itemid = DoGetNext(itemid, Next_Visible);
        }

        // and try all the items (stop when we get to the one we started from)
        while ( itemid.IsOk() && itemid != idParent &&
                    !GetItemText(itemid).Lower().StartsWith(prefix) )
        {
            itemid = DoGetNext(itemid, Next_Visible);
        }
        // If we haven't found the item but wrapped back to the one we started
        // from, id.IsOk() must be false
        if ( itemid == idParent )
        {
            itemid = wxTreeItemId();
        }
    }

    return itemid;
}

// -----------------------------------------------------------------------------
// operations
// -----------------------------------------------------------------------------

wxTreeItemId wxGenericTreeCtrl::DoInsertItem(const wxTreeItemId& parentId,
                                             size_t previous,
                                             const wxString& text,
                                             int image,
                                             int selImage,
                                             wxTreeItemData *data)
{
    wxGenericTreeItem *parent = GetItemPtr(parentId);
    if ( !parent )
    {
        // should we give a warning here?
        return AddRoot(text, image, selImage, data);
    }

    m_dirty = true;     // do this first so stuff below doesn't cause flicker

    wxGenericTreeItem *item =
        new wxGenericTreeItem( parent, text, image, selImage, data );

    if ( data != nullptr )
    {
        data->m_pItem = item;
    }

    parent->Insert( item, previous == (size_t)-1 ? parent->GetChildren().size()
                                                 : previous );

    InvalidateBestSize();
    return item;
}

wxTreeItemId wxGenericTreeCtrl::AddRoot(const wxString& text,
                                        int image,
                                        int selImage,
                                        wxTreeItemData *data)
{
    wxCHECK_MSG( !m_anchor, wxTreeItemId(), "tree can have only one root" );

    m_dirty = true;     // do this first so stuff below doesn't cause flicker

    m_anchor = new wxGenericTreeItem(nullptr, text,
                                   image, selImage, data);
    if ( data != nullptr )
    {
        data->m_pItem = m_anchor;
    }

    if (HasFlag(wxTR_HIDE_ROOT))
    {
        // if root is hidden, make sure we can navigate
        // into children
        m_anchor->SetHasPlus();
        m_anchor->Expand();
        CalculatePositions();
    }

    if (!HasFlag(wxTR_MULTIPLE))
    {
        m_current = m_key_current = m_anchor;
        m_current->SetHilight( true );
    }

    InvalidateBestSize();
    return m_anchor;
}

wxTreeItemId wxGenericTreeCtrl::DoInsertAfter(const wxTreeItemId& parentId,
                                              const wxTreeItemId& idPrevious,
                                              const wxString& text,
                                              int image, int selImage,
                                              wxTreeItemData *data)
{
    wxGenericTreeItem *parent = GetItemPtr(parentId);
    if ( !parent )
    {
        // should we give a warning here?
        return AddRoot(text, image, selImage, data);
    }

    int index = wxNOT_FOUND;
    if (idPrevious.IsOk())
    {
        index = FindItemIndex(parent->GetChildren(), GetItemPtr(idPrevious));
        wxASSERT_MSG( index != wxNOT_FOUND,
                      "previous item in wxGenericTreeCtrl::InsertItem() "
                      "is not a sibling" );
    }

    return DoInsertItem(parentId, (size_t)++index, text, image, selImage, data);
}


void wxGenericTreeCtrl::SendDeleteEvent(wxGenericTreeItem *item)
{
    wxTreeEvent event(wxEVT_TREE_DELETE_ITEM, this, item);
    GetEventHandler()->ProcessEvent( event );
}

// Don't leave edit or selection on a child which is about to disappear
void wxGenericTreeCtrl::ChildrenClosing(wxGenericTreeItem* item)
{
    if ( m_textCtrl && item != m_textCtrl->item() &&
            IsDescendantOf(item, m_textCtrl->item()) )
    {
        m_textCtrl->EndEdit( true );
    }

    if ( item != m_key_current && IsDescendantOf(item, m_key_current) )
    {
        m_key_current = nullptr;
    }

    if ( IsDescendantOf(item, m_select_me) )
    {
        m_select_me = item;
    }

    if ( item != m_current && IsDescendantOf(item, m_current) )
    {
        // Don't leave the only selected item invisible, but do leave selected
        // items selected if we can have many of them.
        if ( !HasFlag(wxTR_MULTIPLE) )
            m_current->SetHilight( false );
        m_current = nullptr;
        m_select_me = item;
    }
}

void wxGenericTreeCtrl::DeleteChildren(const wxTreeItemId& itemId)
{
    m_dirty = true;     // do this first so stuff below doesn't cause flicker

    wxGenericTreeItem *item = GetItemPtr(itemId);
    ChildrenClosing(item);
    item->DeleteChildren(this);
    InvalidateBestSize();
}

void wxGenericTreeCtrl::Delete(const wxTreeItemId& itemId)
{
    m_dirty = true;     // do this first so stuff below doesn't cause flicker

    wxGenericTreeItem *item = GetItemPtr(itemId);

    if (m_textCtrl != nullptr && IsDescendantOf(item, m_textCtrl->item()))
    {
        // can't delete the item being edited, cancel editing it first
        m_textCtrl->EndEdit( true );
    }

    wxGenericTreeItem *parent = item->GetParent();

    // if the selected item will be deleted, select the parent ...
    wxGenericTreeItem *to_be_selected = parent;
    if (parent)
    {
        // .. unless there is a next sibling like wxMSW does it
        const auto& siblings = parent->GetChildren();
        const int pos = FindItemIndex(siblings, item);
        if ( wxSsize(siblings) > pos+1)
            to_be_selected = siblings[pos+1];
    }

    // don't keep stale pointers around!
    if ( IsDescendantOf(item, m_key_current) )
    {
        // Don't silently change the selection:
        // do it properly in idle time, so event
        // handlers get called.

        // m_key_current = parent;
        m_key_current = nullptr;
    }

    // m_select_me records whether we need to select
    // a different item, in idle time.
    if ( m_select_me && IsDescendantOf(item, m_select_me) )
    {
        m_select_me = to_be_selected;
    }

    if ( IsDescendantOf(item, m_current) )
    {
        // Don't silently change the selection:
        // do it properly in idle time, so event
        // handlers get called.

        // m_current = parent;
        m_current = nullptr;
        m_select_me = to_be_selected;
    }

    // remove the item from the tree
    if ( parent )
    {
        auto& siblings = parent->GetChildren();
        const int index = FindItemIndex(siblings, item);
        if ( index != wxNOT_FOUND )
        {
            siblings.erase(siblings.begin() + index);
        }
    }
    else // deleting the root
    {
        // nothing will be left in the tree
        m_anchor = nullptr;
    }

    // and delete all of its children and the item itself now
    item->DeleteChildren(this);
    SendDeleteEvent(item);

    if (item == m_select_me)
        m_select_me = nullptr;

    delete item;

    InvalidateBestSize();
}

void wxGenericTreeCtrl::DeleteAllItems()
{
    if ( m_anchor )
    {
        Delete(m_anchor);
    }
}

void wxGenericTreeCtrl::Expand(const wxTreeItemId& itemId)
{
    wxGenericTreeItem *item = GetItemPtr(itemId);

    wxCHECK_RET( item, wxT("invalid item in wxGenericTreeCtrl::Expand") );
    wxCHECK_RET( !HasFlag(wxTR_HIDE_ROOT) || itemId != GetRootItem(),
                 wxT("can't expand hidden root") );

    if ( !item->HasPlus() )
        return;

    if ( item->IsExpanded() )
        return;

    wxTreeEvent event(wxEVT_TREE_ITEM_EXPANDING, this, item);

    if ( GetEventHandler()->ProcessEvent( event ) && !event.IsAllowed() )
    {
        // cancelled by program
        return;
    }

    item->Expand();
    if ( !IsFrozen() )
    {
        CalculatePositions();

        RefreshSubtree(item);
    }
    else // frozen
    {
        m_dirty = true;
    }

    // Don't send EXPANDED event unconditionally: if this is an item for which
    // SetItemHasChildren(true) had been called before, but no children have
    // been added from the EXPANDING handler, we shouldn't consider the item to
    // be really expanded.
    wxTreeItemIdValue cookie;
    if ( GetFirstChild(item, cookie).IsOk() )
    {
        event.SetEventType(wxEVT_TREE_ITEM_EXPANDED);
        GetEventHandler()->ProcessEvent( event );
    }
}

void wxGenericTreeCtrl::Collapse(const wxTreeItemId& itemId)
{
    wxCHECK_RET( !HasFlag(wxTR_HIDE_ROOT) || itemId != GetRootItem(),
                 wxT("can't collapse hidden root") );

    wxGenericTreeItem *item = GetItemPtr(itemId);

    if ( !item->IsExpanded() )
        return;

    wxTreeEvent event(wxEVT_TREE_ITEM_COLLAPSING, this, item);
    if ( GetEventHandler()->ProcessEvent( event ) && !event.IsAllowed() )
    {
        // cancelled by program
        return;
    }

    ChildrenClosing(item);
    item->Collapse();

#if 0  // TODO why should items be collapsed recursively?
    wxGenericTreeItems& children = item->GetChildren();
    size_t count = children.size();
    for ( size_t n = 0; n < count; n++ )
    {
        Collapse(children[n]);
    }
#endif

    CalculatePositions();

    RefreshSubtree(item);

    event.SetEventType(wxEVT_TREE_ITEM_COLLAPSED);
    GetEventHandler()->ProcessEvent( event );
}

void wxGenericTreeCtrl::CollapseAndReset(const wxTreeItemId& item)
{
    Collapse(item);
    DeleteChildren(item);
}

void wxGenericTreeCtrl::Toggle(const wxTreeItemId& itemId)
{
    wxGenericTreeItem *item = GetItemPtr(itemId);

    if (item->IsExpanded())
        Collapse(itemId);
    else
        Expand(itemId);
}

void wxGenericTreeCtrl::Unselect()
{
    if (m_current)
    {
        m_current->SetHilight( false );
        RefreshLine( m_current );

        m_current = nullptr;
        m_select_me = nullptr;
    }
}

void wxGenericTreeCtrl::ClearFocusedItem()
{
    wxTreeItemId item = GetFocusedItem();
    if ( item.IsOk() )
        SelectItem(item, false);

    m_current = nullptr;
}

void wxGenericTreeCtrl::SetFocusedItem(const wxTreeItemId& item)
{
    wxCHECK_RET( item.IsOk(), wxT("invalid tree item") );

    SelectItem(item, true);
}

void wxGenericTreeCtrl::UnselectAllChildren(wxGenericTreeItem *item)
{
    if (item->IsSelected())
    {
        item->SetHilight(false);
        RefreshLine(item);
    }

    if (item->HasChildren())
    {
        wxGenericTreeItems& children = item->GetChildren();
        size_t count = children.size();
        for ( size_t n = 0; n < count; ++n )
        {
            UnselectAllChildren(children[n]);
        }
    }
}

void wxGenericTreeCtrl::UnselectAll()
{
    wxTreeItemId rootItem = GetRootItem();

    // the tree might not have the root item at all
    if ( rootItem )
    {
        UnselectAllChildren(GetItemPtr(rootItem));
    }
}

void wxGenericTreeCtrl::SelectChildren(const wxTreeItemId& parent)
{
    wxCHECK_RET( HasFlag(wxTR_MULTIPLE),
                 "this only works with multiple selection controls" );

    UnselectAll();

    if ( !HasChildren(parent) )
        return;


    wxGenericTreeItems& children = GetItemPtr(parent)->GetChildren();
    size_t count = children.size();

    wxGenericTreeItem * item = children[0];
    wxTreeEvent event(wxEVT_TREE_SEL_CHANGING, this, item);
    event.m_itemOld = m_current;

    if ( GetEventHandler()->ProcessEvent( event ) && !event.IsAllowed() )
        return;

    for ( size_t n = 0; n < count; ++n )
    {
        m_current = m_key_current = children[n];
        m_current->SetHilight(true);
        RefreshSelected();
    }


    event.SetEventType(wxEVT_TREE_SEL_CHANGED);
    GetEventHandler()->ProcessEvent( event );
}


// Recursive function !
// To stop we must have crt_item<last_item
// Algorithm :
// Tag all next children, when no more children,
// Move to parent (not to tag)
// Keep going... if we found last_item, we stop.
bool
wxGenericTreeCtrl::TagNextChildren(wxGenericTreeItem *crt_item,
                                   wxGenericTreeItem *last_item,
                                   bool select)
{
    wxGenericTreeItem *parent = crt_item->GetParent();

    if (parent == nullptr) // This is root item
        return TagAllChildrenUntilLast(crt_item, last_item, select);

    wxGenericTreeItems& children = parent->GetChildren();
    const int index = FindItemIndex(children, crt_item);
    wxASSERT( index != wxNOT_FOUND ); // I'm not a child of my parent?

    size_t count = children.size();
    for (size_t n=(size_t)(index+1); n<count; ++n)
    {
        if ( TagAllChildrenUntilLast(children[n], last_item, select) )
            return true;
    }

    return TagNextChildren(parent, last_item, select);
}

bool
wxGenericTreeCtrl::TagAllChildrenUntilLast(wxGenericTreeItem *crt_item,
                                           wxGenericTreeItem *last_item,
                                           bool select)
{
    crt_item->SetHilight(select);
    RefreshLine(crt_item);

    if (crt_item==last_item)
        return true;

    // We should leave the not shown children of collapsed items alone.
    if (crt_item->HasChildren() && crt_item->IsExpanded())
    {
        wxGenericTreeItems& children = crt_item->GetChildren();
        size_t count = children.size();
        for ( size_t n = 0; n < count; ++n )
        {
            if (TagAllChildrenUntilLast(children[n], last_item, select))
                return true;
        }
    }

  return false;
}

void
wxGenericTreeCtrl::SelectItemRange(wxGenericTreeItem *item1,
                                   wxGenericTreeItem *item2)
{
    m_select_me = nullptr;

    // item2 is not necessary after item1
    // choice first' and 'last' between item1 and item2
    wxGenericTreeItem *first= (item1->GetY()<item2->GetY()) ? item1 : item2;
    wxGenericTreeItem *last = (item1->GetY()<item2->GetY()) ? item2 : item1;

    bool select = m_current->IsSelected();

    if ( TagAllChildrenUntilLast(first,last,select) )
        return;

    TagNextChildren(first,last,select);
}

void wxGenericTreeCtrl::DoSelectItem(const wxTreeItemId& itemId,
                                     bool unselect_others,
                                     bool extended_select)
{
    wxCHECK_RET( itemId.IsOk(), wxT("invalid tree item") );

    m_select_me = nullptr;

    bool is_single=!(GetWindowStyleFlag() & wxTR_MULTIPLE);
    wxGenericTreeItem *item = GetItemPtr(itemId);

    //wxCHECK_RET( ( (!unselect_others) && is_single),
    //           wxT("this is a single selection tree") );

    // to keep going anyhow !!!
    if (is_single)
    {
        if (item->IsSelected())
            return; // nothing to do
        unselect_others = true;
        extended_select = false;
    }
    else if ( unselect_others && item->IsSelected() )
    {
        // selection change if there is more than one item currently selected
        wxArrayTreeItemIds selected_items;
        if ( GetSelections(selected_items) == 1 )
            return;
    }

    wxTreeEvent event(wxEVT_TREE_SEL_CHANGING, this, item);
    event.m_itemOld = m_current;
    // TODO : Here we don't send any selection mode yet !

    if ( GetEventHandler()->ProcessEvent( event ) && !event.IsAllowed() )
        return;

    wxTreeItemId parent = GetItemParent( itemId );
    while (parent.IsOk())
    {
        if (!IsExpanded(parent))
            Expand( parent );

        parent = GetItemParent( parent );
    }

    // ctrl press
    if (unselect_others)
    {
        if (is_single)
            Unselect(); // to speed up thing
        else UnselectAll();
    }

    // shift press
    if (extended_select)
    {
        if ( !m_current )
        {
            m_current =
            m_key_current = GetItemPtr(GetRootItem());
        }

        // don't change the mark (m_current)
        SelectItemRange(m_current, item);
    }
    else
    {
        bool select = true; // the default

        // Check if we need to toggle hilight (ctrl mode)
        if (!unselect_others)
            select=!item->IsSelected();

        m_current = m_key_current = item;
        m_current->SetHilight(select);
        RefreshLine( m_current );
    }

    // This can cause idle processing to select the root
    // if no item is selected, so it must be after the
    // selection is set
    if (is_single)
        EnsureVisible( itemId );

    event.SetEventType(wxEVT_TREE_SEL_CHANGED);
    GetEventHandler()->ProcessEvent( event );
}

void wxGenericTreeCtrl::SelectItem(const wxTreeItemId& itemId, bool select)
{
    wxGenericTreeItem * const item = GetItemPtr(itemId);
    wxCHECK_RET( item, wxT("SelectItem(): invalid tree item") );

    if ( select )
    {
        if ( !item->IsSelected() )
            DoSelectItem(itemId, !HasFlag(wxTR_MULTIPLE));
    }
    else // deselect
    {
        wxTreeEvent event(wxEVT_TREE_SEL_CHANGING, this, item);
        if ( GetEventHandler()->ProcessEvent( event ) && !event.IsAllowed() )
            return;

        item->SetHilight(false);
        RefreshLine(item);

        event.SetEventType(wxEVT_TREE_SEL_CHANGED);
        GetEventHandler()->ProcessEvent( event );
    }
}

void wxGenericTreeCtrl::FillArray(wxGenericTreeItem *item,
                                  wxArrayTreeItemIds &array) const
{
    if ( item->IsSelected() )
        array.Add(wxTreeItemId(item));

    if ( item->HasChildren() )
    {
        wxGenericTreeItems& children = item->GetChildren();
        size_t count = children.size();
        for ( size_t n = 0; n < count; ++n )
            FillArray(children[n], array);
    }
}

size_t wxGenericTreeCtrl::GetSelections(wxArrayTreeItemIds &array) const
{
    array.Empty();
    wxTreeItemId idRoot = GetRootItem();
    if ( idRoot.IsOk() )
    {
        FillArray(GetItemPtr(idRoot), array);
    }
    //else: the tree is empty, so no selections

    return array.size();
}

void wxGenericTreeCtrl::EnsureVisible(const wxTreeItemId& item)
{
    wxCHECK_RET( item.IsOk(), wxT("invalid tree item") );

    if (!item.IsOk())
        return;

    wxGenericTreeItem *gitem = GetItemPtr(item);

    // first expand all parent branches
    wxGenericTreeItem *parent = gitem->GetParent();

    if ( HasFlag(wxTR_HIDE_ROOT) )
    {
        while ( parent && parent != m_anchor )
        {
            Expand(parent);
            parent = parent->GetParent();
        }
    }
    else
    {
        while ( parent )
        {
            Expand(parent);
            parent = parent->GetParent();
        }
    }

    ScrollTo(item);
}

void wxGenericTreeCtrl::ScrollTo(const wxTreeItemId &item)
{
    if (!item.IsOk())
        return;

    // update the control before scrolling it
    if (m_dirty)
    {
#if defined( __WXMSW__ )
        Update();
#elif defined(__WXMAC__)
        Update();
        DoDirtyProcessing();
#else
        DoDirtyProcessing();
#endif
    }

    wxGenericTreeItem *gitem = GetItemPtr(item);

    int itemY = gitem->GetY();

    int start_x = 0;
    int start_y = 0;
    GetViewStart( &start_x, &start_y );

    const int clientHeight = GetClientSize().y;

    const int itemHeight = GetLineHeight(gitem) + 2;

    if ( itemY + itemHeight > start_y*PIXELS_PER_UNIT + clientHeight )
    {
        // need to scroll down by enough to show this item fully
        itemY += itemHeight - clientHeight;

        // because itemY below will be divided by PIXELS_PER_UNIT it may
        // be rounded down, with the result of the item still only being
        // partially visible, so make sure we are rounding up
        itemY += PIXELS_PER_UNIT - 1;
    }
    else if ( itemY > start_y*PIXELS_PER_UNIT )
    {
        // item is already fully visible, don't do anything
        return;
    }
    //else: scroll up to make this item the top one displayed

    Scroll(-1, itemY/PIXELS_PER_UNIT);
}

void wxGenericTreeCtrl::SortChildren(const wxTreeItemId& itemId)
{
    wxCHECK_RET( itemId.IsOk(), wxT("invalid tree item") );

    wxGenericTreeItem *item = GetItemPtr(itemId);

    wxGenericTreeItems& children = item->GetChildren();
    if ( children.size() > 1 )
    {
        m_dirty = true;

        std::sort(children.begin(), children.end(),
                  [this](wxGenericTreeItem* a, wxGenericTreeItem* b)
                  {
                      return OnCompareItems(a, b) < 0;
                  });
    }
    //else: don't make the tree dirty as nothing changed
}

void wxGenericTreeCtrl::CalculateLineHeight()
{
    wxInfoDC dc(this);
    m_lineHeight = dc.GetCharHeight() + FromDIP(4);

    if ( HasImages() )
    {
        // Calculate a m_lineHeight value from the normal Image sizes.
        m_lineHeight = GetImageLogicalSize(this).y;
    }

    if ( m_imagesState.HasImages() )
    {
        // Calculate a m_lineHeight value from the state Image sizes.
        // May be toggle off. Then wxGenericTreeCtrl will spread when
        // necessary (which might look ugly).
        const int height = m_imagesState.GetImageLogicalSize(this).y;
        if (height > m_lineHeight)
            m_lineHeight = height;
    }

    if ( m_imagesButtons.HasImages() )
    {
        // Calculate a m_lineHeight value from the Button image sizes.
        // May be toggle off. Then wxGenericTreeCtrl will spread when
        // necessary (which might look ugly).
        const int height = m_imagesButtons.GetImageLogicalSize(this).y;
        if (height > m_lineHeight)
            m_lineHeight = height;
    }

    m_lineHeight += FromDIP(2); // Add some extra interline space.
}

void wxGenericTreeCtrl::OnImagesChanged()
{
    // We call it solely for the side effect of updating the image list,
    // which may be used by the application code using this class, even if
    // we don't use it ourselves, but it also has an important side effect
    // of ensuring that we can always get the size to use for the images.
    GetUpdatedImageListFor(this);

    m_imagesState.GetUpdatedImageListFor(this);

    UpdateAfterImageListChange();
}

void wxGenericTreeCtrl::UpdateAfterImageListChange()
{
    m_dirty = true;

    if (m_anchor)
        m_anchor->RecursiveResetSize();

    // Don't do this if we're in the process of deleting the tree control.
    if (HasImages())
        CalculateLineHeight();
}

void wxGenericTreeCtrl::SetImageList(wxImageList *imageList)
{
    wxWithImages::SetImageList(imageList);
    UpdateAfterImageListChange();
}

void wxGenericTreeCtrl::SetStateImages(const wxVector<wxBitmapBundle>& images)
{
    m_imagesState.SetImages(images);

    // As above, only call it for the side effect of updating the image list.
    m_imagesState.GetUpdatedImageListFor(this);

    UpdateAfterImageListChange();
}

void wxGenericTreeCtrl::SetStateImageList(wxImageList *imageList)
{
    m_imagesState.SetImageList(imageList);
    UpdateAfterImageListChange();
}

void wxGenericTreeCtrl::SetButtonsImageList(wxImageList *imageList)
{
    m_imagesButtons.SetImageList(imageList);
    UpdateAfterImageListChange();
}

void wxGenericTreeCtrl::AssignButtonsImageList(wxImageList *imageList)
{
    SetButtonsImageList(imageList);
    m_imagesButtons.TakeOwnership();
}

// -----------------------------------------------------------------------------
// helpers
// -----------------------------------------------------------------------------

void wxGenericTreeCtrl::AdjustMyScrollbars()
{
    if (m_anchor)
    {
        int x = 0, y = 0;
        m_anchor->GetSize( x, y, this );
        y += PIXELS_PER_UNIT+2; // one more scrollbar unit + 2 pixels
        x += PIXELS_PER_UNIT+2; // one more scrollbar unit + 2 pixels
        int x_pos = GetScrollPos( wxHORIZONTAL );
        int y_pos = GetScrollPos( wxVERTICAL );
        SetScrollbars( PIXELS_PER_UNIT, PIXELS_PER_UNIT,
                       x/PIXELS_PER_UNIT, y/PIXELS_PER_UNIT,
                       x_pos, y_pos );
    }
    else
    {
        SetScrollbars( 0, 0, 0, 0 );
    }
}

int wxGenericTreeCtrl::GetLineHeight(wxGenericTreeItem *item) const
{
    if (GetWindowStyleFlag() & wxTR_HAS_VARIABLE_ROW_HEIGHT)
        return item->GetHeight();
    else
        return m_lineHeight;
}

void wxGenericTreeCtrl::PaintItem(wxGenericTreeItem *item, wxDC& dc)
{
    item->SetFont(this, dc);
    item->CalculateSize(this, dc);

    wxCoord text_h = item->GetTextHeight();

    int image_h = 0, image_w = 0;
    int image = item->GetCurrentImage();
    if ( image != NO_IMAGE )
    {
        if ( HasImages() )
        {
            const wxSize imageSize = GetImageLogicalSize(this);
            image_h = imageSize.y;
            image_w = imageSize.x + MARGIN_BETWEEN_IMAGE_AND_TEXT;
        }
        else
        {
            image = NO_IMAGE;
        }
    }

    int state_h = 0, state_w = 0;
    int state = item->GetState();
    if ( state != wxTREE_ITEMSTATE_NONE )
    {
        if ( m_imagesState.HasImages() )
        {
            m_imagesState.GetImageLogicalSize(this, state_w, state_h);
            if ( image_w != 0 )
                state_w += MARGIN_BETWEEN_STATE_AND_IMAGE;
            else
                state_w += MARGIN_BETWEEN_IMAGE_AND_TEXT;
        }
        else
        {
            state = wxTREE_ITEMSTATE_NONE;
        }
    }

    int total_h = GetLineHeight(item);
    bool drawItemBackground = false,
         hasBgColour = false;

    if ( item->IsSelected() )
    {
        dc.SetBrush(m_hasFocus ? m_hilightBrush : m_hilightUnfocusedBrush);
        drawItemBackground = true;
    }
    else
    {
        wxColour colBg;
        wxItemAttr * const attr = item->GetAttributes();
        if ( attr && attr->HasBackgroundColour() )
        {
            drawItemBackground =
            hasBgColour = true;
            colBg = attr->GetBackgroundColour();
        }
        else
        {
            colBg = GetBackgroundColour();
        }
        dc.SetBrush(wxBrush(colBg, wxBRUSHSTYLE_SOLID));
    }

    int offset = HasFlag(wxTR_ROW_LINES) ? 1 : 0;

    if ( HasFlag(wxTR_FULL_ROW_HIGHLIGHT) )
    {
        int x, w, h;
        x=0;
        GetVirtualSize(&w, &h);
        wxRect rect( x, item->GetY()+offset, w, total_h-offset);
        if (!item->IsSelected())
        {
            dc.DrawRectangle(rect);
        }
        else
        {
            int flags = wxCONTROL_SELECTED;
            if (m_hasFocus)
                flags |= wxCONTROL_FOCUSED;
            if ((item == m_current) && (m_hasFocus))
                flags |= wxCONTROL_CURRENT;

            wxRendererNative::Get().
                DrawItemSelectionRect(this, dc, rect, flags);
        }
    }
    else // no full row highlight
    {
        if ( item->IsSelected() &&
                (state != wxTREE_ITEMSTATE_NONE || image != NO_IMAGE) )
        {
            // If it's selected, and there's an state image or normal image,
            // then we should take care to leave the area under the image
            // painted in the background colour.
            wxRect rect( item->GetX() + state_w + image_w - 2,
                         item->GetY() + offset,
                         item->GetWidth() - state_w - image_w + 2,
                         total_h - offset );
            rect.x -= 1;
            rect.width += 2;

            int flags = wxCONTROL_SELECTED;
            if (m_hasFocus)
                flags |= wxCONTROL_FOCUSED;
            if ((item == m_current) && (m_hasFocus))
                flags |= wxCONTROL_CURRENT;
            wxRendererNative::Get().
                DrawItemSelectionRect(this, dc, rect, flags);
        }
        // On GTK+ 2, drawing a 'normal' background is wrong for themes that
        // don't allow backgrounds to be customized. Not drawing the background,
        // except for custom item backgrounds, works for both kinds of theme.
        else if (drawItemBackground)
        {
            wxRect rect( item->GetX() + state_w + image_w - 2,
                         item->GetY() + offset,
                         item->GetWidth() - state_w - image_w + 2,
                         total_h - offset );
            if ( hasBgColour )
            {
                dc.DrawRectangle( rect );
            }
            else // no specific background colour
            {
                rect.x -= 1;
                rect.width += 2;

                int flags = wxCONTROL_SELECTED;
                if (m_hasFocus)
                    flags |= wxCONTROL_FOCUSED;
                if ((item == m_current) && (m_hasFocus))
                    flags |= wxCONTROL_CURRENT;
                wxRendererNative::Get().
                    DrawItemSelectionRect(this, dc, rect, flags);
            }
        }
    }

    if ( state != wxTREE_ITEMSTATE_NONE )
    {
        wxDCClipper clip(dc, item->GetX(), item->GetY(), state_w, total_h);

        wxDrawImageBitmap(this, m_imagesState, state,
                          dc,
                          item->GetX(),
                          item->GetY() +
                          (total_h > state_h ? (total_h-state_h)/2 : 0));
    }

    if ( image != NO_IMAGE )
    {
        wxDCClipper clip(dc, item->GetX() + state_w, item->GetY(),
                             image_w, total_h);
        wxDrawImageBitmap(this, image,
                          dc,
                          item->GetX() + state_w,
                          item->GetY() +
                          (total_h > image_h ? (total_h-image_h)/2 : 0));
    }

    dc.SetBackgroundMode(wxBRUSHSTYLE_TRANSPARENT);
    int extraH = (total_h > text_h) ? (total_h - text_h)/2 : 0;
    dc.DrawText( item->GetText(),
                 (wxCoord)(state_w + image_w + item->GetX()),
                 (wxCoord)(item->GetY() + extraH));

    // restore normal font
    dc.SetFont( m_font );

    if (item == m_dndEffectItem)
    {
        dc.SetPen( *wxBLACK_PEN );
        // DnD visual effects
        switch (m_dndEffect)
        {
            case BorderEffect:
            {
                dc.SetBrush(*wxTRANSPARENT_BRUSH);
                int w = item->GetWidth() + 2;
                int h = total_h + 2;
                dc.DrawRectangle( item->GetX() - 1, item->GetY() - 1, w, h);
                break;
            }
            case AboveEffect:
            {
                int x = item->GetX(),
                    y = item->GetY();
                dc.DrawLine( x, y, x + item->GetWidth(), y);
                break;
            }
            case BelowEffect:
            {
                int x = item->GetX(),
                    y = item->GetY();
                y += total_h - 1;
                dc.DrawLine( x, y, x + item->GetWidth(), y);
                break;
            }
            case NoEffect:
                break;
        }
    }
}

void
wxGenericTreeCtrl::PaintLevel(wxGenericTreeItem *item,
                              wxDC &dc,
                              int level,
                              int &y)
{
    int indent = FromDIP(m_indent);
    int spacing = FromDIP(m_spacing);

    int x = level*indent;
    if (!HasFlag(wxTR_HIDE_ROOT))
    {
        x += indent;
    }
    else if (level == 0)
    {
        // always expand hidden root
        int origY = y;
        wxGenericTreeItems& children = item->GetChildren();
        int count = children.size();
        if (count > 0)
        {
            int n = 0, oldY;
            do {
                oldY = y;
                PaintLevel(children[n], dc, 1, y);
            } while (++n < count);

            if ( !HasFlag(wxTR_NO_LINES) && HasFlag(wxTR_LINES_AT_ROOT)
                    && count > 0 )
            {
                // draw line down to last child
                origY += GetLineHeight(children[0])>>1;
                oldY += GetLineHeight(children[n-1])>>1;
                dc.DrawLine(3, origY, 3, oldY);
            }
        }
        return;
    }

    item->SetX(x+spacing);
    item->SetY(y);

    int h = GetLineHeight(item);
    int y_top = y;
    int y_mid = y_top + (h>>1);
    y += h;

    int exposed_x = dc.LogicalToDeviceX(0);
    int exposed_y = dc.LogicalToDeviceY(y_top);

    if (IsExposed(exposed_x, exposed_y, 10000, h))  // 10000 = very much
    {
        const wxPen *pen =
#ifndef __WXMAC__
            // don't draw rect outline if we already have the
            // background color under Mac
            (item->IsSelected() && m_hasFocus) ? wxBLACK_PEN :
#endif // !__WXMAC__
            wxTRANSPARENT_PEN;

        wxColour colText;
        if ( item->IsSelected() )
        {
#ifdef __WXMAC__
            if (m_hasFocus)
               colText = *wxWHITE;
#else
            colText = wxSystemSettings::GetColour(wxSYS_COLOUR_LISTBOXHIGHLIGHTTEXT);
#endif
        }
        else
        {
            wxItemAttr *attr = item->GetAttributes();
            if (attr && attr->HasTextColour())
                colText = attr->GetTextColour();
            else
                colText = GetForegroundColour();
        }

        // prepare to draw
        dc.SetTextForeground(colText);
        dc.SetPen(*pen);

        // draw
        PaintItem(item, dc);

        if (HasFlag(wxTR_ROW_LINES))
        {
            dc.SetPen(wxSystemSettings::GetColour(wxSYS_COLOUR_GRAYTEXT));
            dc.DrawLine(0, y_top, 10000, y_top);
            dc.DrawLine(0, y, 10000, y);
        }

        // restore DC objects
        dc.SetBrush(*wxWHITE_BRUSH);
        dc.SetPen(m_dottedPen);
        dc.SetTextForeground(*wxBLACK);

        if ( !HasFlag(wxTR_NO_LINES) )
        {
            // draw the horizontal line here
            int x_start = x;
            if (x > (int)indent)
                x_start -= indent;
            else if (HasFlag(wxTR_LINES_AT_ROOT))
                x_start = 3;
            dc.DrawLine(x_start, y_mid, x + spacing, y_mid);
        }

        // should the item show a button?
        if ( item->HasPlus() && HasButtons() )
        {
            if ( m_imagesButtons.HasImages() )
            {
                // draw the image button here
                int image = item->IsExpanded() ? wxTreeItemIcon_Expanded
                                               : wxTreeItemIcon_Normal;
                if ( item->IsSelected() )
                    image += wxTreeItemIcon_Selected - wxTreeItemIcon_Normal;

                int image_w, image_h;
                m_imagesButtons.GetImageLogicalSize(this, image_w, image_h);
                int xx = x - image_w/2;
                int yy = y_mid - image_h/2;

                wxDCClipper clip(dc, xx, yy, image_w, image_h);
                wxDrawImageBitmap(this, m_imagesButtons, image, dc, xx, yy);
            }
            else // no custom buttons
            {
                const int wImage = FromDIP(9);
                const int hImage = FromDIP(9);

                int flag = 0;
                if (item->IsExpanded())
                    flag |= wxCONTROL_EXPANDED;
                if (item == m_underMouse)
                    flag |= wxCONTROL_CURRENT;
                if (item->IsSelected())
                    flag |= wxCONTROL_SELECTED;

                wxRendererNative::Get().DrawTreeItemButton
                                        (
                                            this,
                                            dc,
                                            wxRect(x - wImage/2,
                                                   y_mid - hImage/2,
                                                   wImage, hImage),
                                            flag
                                        );
            }
        }
    }

    if (item->IsExpanded())
    {
        wxGenericTreeItems& children = item->GetChildren();
        int count = children.size();
        if (count > 0)
        {
            int n = 0, oldY;
            ++level;
            do {
                oldY = y;
                PaintLevel(children[n], dc, level, y);
            } while (++n < count);

            if (!HasFlag(wxTR_NO_LINES) && count > 0)
            {
                // draw line down to last child
                oldY += GetLineHeight(children[n-1])>>1;
                if (HasButtons())
                    y_mid += 5;

                // Only draw the portion of the line that is visible, in case
                // it is huge
                wxCoord xOrigin=0, yOrigin=0, width, height;
                dc.GetDeviceOrigin(&xOrigin, &yOrigin);
                yOrigin = abs(yOrigin);
                GetClientSize(&width, &height);

                // Move end points to the beginning/end of the view?
                if (y_mid < yOrigin)
                    y_mid = yOrigin;
                if (oldY > yOrigin + height)
                    oldY = yOrigin + height;

                // after the adjustments if y_mid is larger than oldY then the
                // line isn't visible at all so don't draw anything
                if (y_mid < oldY)
                    dc.DrawLine(x, y_mid, x, oldY);
            }
        }
    }
}

void wxGenericTreeCtrl::DrawDropEffect(wxGenericTreeItem *item)
{
    if ( item )
    {
        if ( item->HasPlus() )
        {
            // it's a folder, indicate it by a border
            DrawBorder(item);
        }
        else
        {
            // draw a line under the drop target because the item will be
            // dropped there
            DrawLine(item, !m_dropEffectAboveItem );
        }

        SetCursor(*wxSTANDARD_CURSOR);
    }
    else
    {
        // can't drop here
        SetCursor(wxCURSOR_NO_ENTRY);
    }
}

void wxGenericTreeCtrl::DrawBorder(const wxTreeItemId &item)
{
    wxCHECK_RET( item.IsOk(), "invalid item in wxGenericTreeCtrl::DrawLine" );

    wxGenericTreeItem *i = GetItemPtr(item);

    if (m_dndEffect == NoEffect)
    {
        m_dndEffect = BorderEffect;
        m_dndEffectItem = i;
    }
    else
    {
        m_dndEffect = NoEffect;
        m_dndEffectItem = nullptr;
    }

    wxRect rect( i->GetX()-1, i->GetY()-1, i->GetWidth()+2, GetLineHeight(i)+2 );
    CalcScrolledPosition( rect.x, rect.y, &rect.x, &rect.y );
    RefreshRect( rect );
}

void wxGenericTreeCtrl::DrawLine(const wxTreeItemId &item, bool below)
{
    wxCHECK_RET( item.IsOk(), "invalid item in wxGenericTreeCtrl::DrawLine" );

    wxGenericTreeItem *i = GetItemPtr(item);

    if (m_dndEffect == NoEffect)
    {
        if (below)
            m_dndEffect = BelowEffect;
        else
            m_dndEffect = AboveEffect;
        m_dndEffectItem = i;
    }
    else
    {
        m_dndEffect = NoEffect;
        m_dndEffectItem = nullptr;
    }

    wxRect rect( i->GetX()-1, i->GetY()-1, i->GetWidth()+2, GetLineHeight(i)+2 );
    CalcScrolledPosition( rect.x, rect.y, &rect.x, &rect.y );
    RefreshRect( rect );
}

// -----------------------------------------------------------------------------
// wxWidgets callbacks
// -----------------------------------------------------------------------------

void wxGenericTreeCtrl::OnSize( wxSizeEvent &event )
{
    if (HasFlag( wxTR_FULL_ROW_HIGHLIGHT) && m_current)
        RefreshLine( m_current );

    event.Skip(true);
}

void wxGenericTreeCtrl::OnPaint( wxPaintEvent &WXUNUSED(event) )
{
    wxPaintDC dc(this);
    PrepareDC( dc );

    if ( !m_anchor)
        return;

    dc.SetPen( m_dottedPen );

    int y = 2;
    PaintLevel( m_anchor, dc, 0, y );
}

void wxGenericTreeCtrl::OnSetFocus( wxFocusEvent &event )
{
    m_hasFocus = true;

    RefreshSelected();

    event.Skip();
}

void wxGenericTreeCtrl::OnKillFocus( wxFocusEvent &event )
{
    m_hasFocus = false;

    RefreshSelected();

    event.Skip();
}

void wxGenericTreeCtrl::OnKeyDown( wxKeyEvent &event )
{
    // send a tree event
    wxTreeEvent te( wxEVT_TREE_KEY_DOWN, this);
    te.m_evtKey = event;
    if ( GetEventHandler()->ProcessEvent( te ) )
        return;

    event.Skip();
}

void wxGenericTreeCtrl::OnChar( wxKeyEvent &event )
{
    if ( (m_current == nullptr) || (m_key_current == nullptr) )
    {
        event.Skip();
        return;
    }

    // how should the selection work for this event?
    bool is_multiple, extended_select, unselect_others;
    EventFlagsToSelType(GetWindowStyleFlag(),
                        event.ShiftDown(),
                        event.CmdDown(),
                        is_multiple, extended_select, unselect_others);

    if (GetLayoutDirection() == wxLayout_RightToLeft)
    {
        if (event.GetKeyCode() == WXK_RIGHT)
            event.m_keyCode = WXK_LEFT;
        else if (event.GetKeyCode() == WXK_LEFT)
            event.m_keyCode = WXK_RIGHT;
    }

    // + : Expand
    // - : Collaspe
    // * : Expand all/Collapse all
    // ' ' | return : activate
    // up    : go up (not last children!)
    // down  : go down
    // left  : collapse or go to parent
    // right : expand or go to first child
    // home  : go to root
    // end   : go to last item without opening parents
    // alnum : start or continue searching for the item with this prefix
    int keyCode = event.GetKeyCode();

#ifdef __WXOSX__
    // Make the keys work as they do in the native control:
    // right => expand
    // left => collapse if current item is expanded
    if (keyCode == WXK_RIGHT)
    {
        keyCode = '+';
    }
    else if (keyCode == WXK_LEFT && IsExpanded(m_current))
    {
        keyCode = '-';
    }
#endif // __WXOSX__

    switch ( keyCode )
    {
        case '+':
        case WXK_ADD:
            if (m_current->HasPlus() && !IsExpanded(m_current))
            {
                Expand(m_current);
            }
            break;

        case '*':
        case WXK_MULTIPLY:
            if ( !IsExpanded(m_current) )
            {
                // expand all
                ExpandAllChildren(m_current);
                break;
            }
            wxFALLTHROUGH;//else: fall through to Collapse() it

        case '-':
        case WXK_SUBTRACT:
            if (IsExpanded(m_current))
            {
                Collapse(m_current);
            }
            break;

        case WXK_MENU:
            {
                // Use the item's bounding rectangle to determine position for
                // the event
                wxRect ItemRect;
                GetBoundingRect(m_current, ItemRect, true);

                wxTreeEvent
                    eventMenu(wxEVT_TREE_ITEM_MENU, this, m_current);
                // Use the left edge, vertical middle
                eventMenu.m_pointDrag = wxPoint(ItemRect.GetX(),
                                                ItemRect.GetY() +
                                                    ItemRect.GetHeight() / 2);
                GetEventHandler()->ProcessEvent( eventMenu );
            }
            break;

        case ' ':
        case WXK_RETURN:
            if ( !event.HasModifiers() )
            {
                wxTreeEvent
                   eventAct(wxEVT_TREE_ITEM_ACTIVATED, this, m_current);
                GetEventHandler()->ProcessEvent( eventAct );
            }

            // in any case, also generate the normal key event for this key,
            // even if we generated the ACTIVATED event above: this is what
            // wxMSW does and it makes sense because you might not want to
            // process ACTIVATED event at all and handle Space and Return
            // directly (and differently) which would be impossible otherwise
            event.Skip();
            break;

            // up goes to the previous sibling or to the last
            // of its children if it's expanded
        case WXK_UP:
            {
                wxTreeItemId prev = GetPrevSibling( m_key_current );
                if (!prev)
                {
                    prev = GetItemParent( m_key_current );
                    if ((prev == GetRootItem()) && HasFlag(wxTR_HIDE_ROOT))
                    {
                        break;  // don't go to root if it is hidden
                    }
                    if (prev)
                    {
                        wxTreeItemIdValue cookie;
                        wxTreeItemId current = m_key_current;
                        // TODO: Huh?  If we get here, we'd better be the first
                        // child of our parent.  How else could it be?
                        if (current == GetFirstChild( prev, cookie ))
                        {
                            // otherwise we return to where we came from
                            DoSelectItem(prev,
                                         unselect_others,
                                         extended_select);
                            m_key_current = GetItemPtr(prev);
                            break;
                        }
                    }
                }
                if (prev)
                {
                    while ( IsExpanded(prev) && HasChildren(prev) )
                    {
                        wxTreeItemId child = GetLastChild(prev);
                        if ( child )
                        {
                            prev = child;
                        }
                    }

                    DoSelectItem( prev, unselect_others, extended_select );
                    m_key_current = GetItemPtr(prev);
                }
            }
            break;

            // left arrow collapses or goes to the parent if it's not expanded
        case WXK_LEFT:
            {
                if (m_current == GetItemPtr(GetRootItem()) && HasFlag(wxTR_HIDE_ROOT))
                {
                    // don't try to collapse hidden root item
                    // (which can be the current one when the tree is empty)
                    break;
                }
                if (IsExpanded(m_current))
                {
                    Collapse(m_current);
                }
                else
                {
                    // select parent unless it's the hidden root
                    wxTreeItemId parent = GetItemParent(m_current);
                    if (parent && (parent != GetRootItem() || !HasFlag(wxTR_HIDE_ROOT)))
                    {
                        DoSelectItem(parent, unselect_others, extended_select);
                    }
                }
            }
            break;

            // right arrow expands or goes to first child if it's already expanded
        case WXK_RIGHT:
            {
                if (m_current == GetItemPtr(GetRootItem()) && HasFlag(wxTR_HIDE_ROOT))
                {
                    // don't try to expand hidden root item
                    // (which can be the current one when the tree is empty)
                    break;
                }
                if (HasChildren(m_current))
                {
                    if (IsExpanded(m_current))
                    {
                        wxTreeItemIdValue cookie;
                        wxTreeItemId child = GetFirstChild(m_current, cookie);
                        if (child)
                        {
                            DoSelectItem(child, unselect_others, extended_select);
                        }
                    }
                    else
                    {
                        Expand(m_current);
                    }
                }
            }
            break;

        case WXK_DOWN:
            {
                if (IsExpanded(m_key_current) && HasChildren(m_key_current))
                {
                    wxTreeItemIdValue cookie;
                    wxTreeItemId child = GetFirstChild( m_key_current, cookie );
                    if ( !child )
                        break;

                    DoSelectItem( child, unselect_others, extended_select );
                    m_key_current = GetItemPtr(child);
                }
                else
                {
                    wxTreeItemId next = GetNextSibling( m_key_current );
                    if (!next)
                    {
                        wxTreeItemId current = m_key_current;
                        while (current.IsOk() && !next)
                        {
                            current = GetItemParent( current );
                            if (current)
                                next = GetNextSibling( current );
                        }
                    }
                    if (next)
                    {
                        DoSelectItem( next, unselect_others, extended_select );
                        m_key_current = GetItemPtr(next);
                    }
                }
            }
            break;

            // <End> selects the last visible tree item
        case WXK_END:
            {
                wxTreeItemId last = GetRootItem();

                while ( last.IsOk() && IsExpanded(last) )
                {
                    wxTreeItemId lastChild = GetLastChild(last);

                    // it may happen if the item was expanded but then all of
                    // its children have been deleted - so IsExpanded() returned
                    // true, but GetLastChild() returned invalid item
                    if ( !lastChild )
                        break;

                    last = lastChild;
                }

                if ( last.IsOk() )
                {
                    DoSelectItem( last, unselect_others, extended_select );
                }
            }
            break;

            // <Home> selects the root item
        case WXK_HOME:
            {
                wxTreeItemId prev = GetRootItem();
                if (!prev)
                    break;

                if ( HasFlag(wxTR_HIDE_ROOT) )
                {
                    wxTreeItemIdValue cookie;
                    prev = GetFirstChild(prev, cookie);
                    if (!prev)
                        break;
                }

                DoSelectItem( prev, unselect_others, extended_select );
            }
            break;

        default:
            // do not use wxIsalnum() here
            if ( !event.HasModifiers() &&
                 ((keyCode >= '0' && keyCode <= '9') ||
                  (keyCode >= 'a' && keyCode <= 'z') ||
                  (keyCode >= 'A' && keyCode <= 'Z') ||
                  (keyCode == '_')))
            {
                // find the next item starting with the given prefix
                wxChar ch = (wxChar)keyCode;
                wxTreeItemId id;

                // if the same character is typed multiple times then go to the
                // next entry starting with that character instead of searching
                // for an item starting with multiple copies of this character,
                // this is more useful and is how it works under Windows.
                if ( m_findPrefix.length() == 1 && m_findPrefix[0] == ch )
                {
                    id = FindItem(m_current, ch);
                }
                else
                {
                    const wxString newPrefix(m_findPrefix + ch);
                    id = FindItem(m_current, newPrefix);
                    if ( id.IsOk() )
                        m_findPrefix = newPrefix;
                }

                // also start the timer to reset the current prefix if the user
                // doesn't press any more alnum keys soon -- we wouldn't want
                // to use this prefix for a new item search
                if ( !m_findTimer )
                {
                    m_findTimer = new wxTreeFindTimer(this);
                }

                // Notice that we should start the timer even if we didn't find
                // anything to make sure we reset the search state later.
                m_findTimer->StartOnce(wxTreeFindTimer::DELAY);

                if ( id.IsOk() )
                {
                    SelectItem(id);

                    // Reset the bell flag if it had been temporarily disabled
                    // before.
                    if ( m_findBell == -1 )
                        m_findBell = 1;
                }
                else // No such item
                {
                    // Signal it with a bell if enabled.
                    if ( m_findBell == 1 )
                    {
                        ::wxBell();

                        // Disable it for the next unsuccessful match, we only
                        // beep once, this is usually enough and continuing to
                        // do it would be annoying.
                        m_findBell = -1;
                    }
                }
            }
            else
            {
                event.Skip();
            }
    }
}

wxTreeItemId
wxGenericTreeCtrl::DoTreeHitTest(const wxPoint& point, int& flags) const
{
    int w, h;
    GetSize(&w, &h);
    flags=0;
    if (point.x<0)
        flags |= wxTREE_HITTEST_TOLEFT;
    if (point.x>w)
        flags |= wxTREE_HITTEST_TORIGHT;
    if (point.y<0)
        flags |= wxTREE_HITTEST_ABOVE;
    if (point.y>h)
        flags |= wxTREE_HITTEST_BELOW;
    if (flags)
        return wxTreeItemId();

    if (m_anchor == nullptr)
    {
        flags = wxTREE_HITTEST_NOWHERE;
        return wxTreeItemId();
    }

    wxGenericTreeItem *hit =  m_anchor->HitTest(CalcUnscrolledPosition(point),
                                                this, flags, 0);
    if (hit == nullptr)
    {
        flags = wxTREE_HITTEST_NOWHERE;
        return wxTreeItemId();
    }
    return hit;
}

// get the bounding rectangle of the item (or of its label only)
bool wxGenericTreeCtrl::GetBoundingRect(const wxTreeItemId& item,
                                        wxRect& rect,
                                        bool textOnly) const
{
    wxCHECK_MSG( item.IsOk(), false,
                 "invalid item in wxGenericTreeCtrl::GetBoundingRect" );

    wxGenericTreeItem *i = GetItemPtr(item);

    if ( textOnly )
    {
        int image_w = 0;
        if ( i->GetCurrentImage() != NO_IMAGE && HasImages() )
        {
            image_w = GetImageLogicalSize(this).x + MARGIN_BETWEEN_IMAGE_AND_TEXT;
        }

        int state_w = 0;
        int state = GetItemPtr(item)->GetState();
        if ( state != wxTREE_ITEMSTATE_NONE && m_imagesState.HasImages() )
        {
            int state_h;
            m_imagesState.GetImageLogicalSize( this, state_w, state_h );
            if ( image_w != 0 )
                state_w += MARGIN_BETWEEN_STATE_AND_IMAGE;
            else
                state_w += MARGIN_BETWEEN_IMAGE_AND_TEXT;
        }

        rect.x = i->GetX() + state_w + image_w;
        rect.width = i->GetWidth() - state_w - image_w;

    }
    else // the entire line
    {
        rect.x = 0;
        rect.width = GetClientSize().x;
    }

    rect.y = i->GetY();
    rect.height = GetLineHeight(i);

    // we have to return the logical coordinates, not physical ones
    rect.SetTopLeft(CalcScrolledPosition(rect.GetTopLeft()));

    return true;
}

wxTextCtrl *wxGenericTreeCtrl::EditLabel(const wxTreeItemId& item,
                                  wxClassInfo * WXUNUSED(textCtrlClass))
{
    wxCHECK_MSG( item.IsOk(), nullptr, wxT("can't edit an invalid item") );

    wxGenericTreeItem *itemEdit = GetItemPtr(item);

    wxTreeEvent te(wxEVT_TREE_BEGIN_LABEL_EDIT, this, itemEdit);
    if ( GetEventHandler()->ProcessEvent( te ) && !te.IsAllowed() )
    {
        // vetoed by user
        return nullptr;
    }

    // We have to call this here because the label in
    // question might just have been added and no screen
    // update taken place.
    if ( m_dirty )
        DoDirtyProcessing();

    // TODO: use textCtrlClass here to create the control of correct class
    m_textCtrl = new wxTreeTextCtrl(this, itemEdit);

    m_textCtrl->SetFocus();

    return m_textCtrl;
}

// returns a pointer to the text edit control if the item is being
// edited, nullptr otherwise (it's assumed that no more than one item may
// be edited simultaneously)
wxTextCtrl* wxGenericTreeCtrl::GetEditControl() const
{
    return m_textCtrl;
}

void wxGenericTreeCtrl::EndEditLabel(const wxTreeItemId& WXUNUSED(item),
                                     bool discardChanges)
{
    if (m_textCtrl)
    {
        m_textCtrl->EndEdit(discardChanges);
    }
}

bool wxGenericTreeCtrl::OnRenameAccept(wxGenericTreeItem *item,
                                       const wxString& value)
{
    wxTreeEvent le(wxEVT_TREE_END_LABEL_EDIT, this, item);
    le.m_label = value;
    le.m_editCancelled = false;

    return !GetEventHandler()->ProcessEvent( le ) || le.IsAllowed();
}

void wxGenericTreeCtrl::OnRenameCancelled(wxGenericTreeItem *item)
{
    // let owner know that the edit was cancelled
    wxTreeEvent le(wxEVT_TREE_END_LABEL_EDIT, this, item);
    le.m_editCancelled = true;

    GetEventHandler()->ProcessEvent( le );
}

void wxGenericTreeCtrl::OnRenameTimer()
{
    EditLabel( m_current );
}

void wxGenericTreeCtrl::OnMouse( wxMouseEvent &event )
{
    if ( !m_anchor )
        return;

    wxPoint pt = CalcUnscrolledPosition(event.GetPosition());

    // Is the mouse over a tree item button?
    int flags = 0;
    wxGenericTreeItem *thisItem = m_anchor->HitTest(pt, this, flags, 0);
    wxGenericTreeItem *underMouse = thisItem;
#if wxUSE_TOOLTIPS
    bool underMouseChanged = (underMouse != m_underMouse) ;
#endif // wxUSE_TOOLTIPS

    if ((underMouse) &&
        (flags & wxTREE_HITTEST_ONITEMBUTTON) &&
        (!event.LeftIsDown()) &&
        (!m_isDragging) &&
        (!m_renameTimer || !m_renameTimer->IsRunning()))
    {
    }
    else
    {
        underMouse = nullptr;
    }

    if (underMouse != m_underMouse)
    {
         if (m_underMouse)
         {
            // unhighlight old item
            wxGenericTreeItem *tmp = m_underMouse;
            m_underMouse = nullptr;
            RefreshLine( tmp );
         }

         m_underMouse = underMouse;
         if (m_underMouse)
            RefreshLine( m_underMouse );
    }

#if wxUSE_TOOLTIPS
    // Determines what item we are hovering over and need a tooltip for
    wxTreeItemId hoverItem = thisItem;

    // We do not want a tooltip if we are dragging, or if the rename timer is
    // running
    if ( underMouseChanged &&
            hoverItem.IsOk() &&
              !m_isDragging &&
                (!m_renameTimer || !m_renameTimer->IsRunning()) )
    {
        // Ask the tree control what tooltip (if any) should be shown
        wxTreeEvent
            hevent(wxEVT_TREE_ITEM_GETTOOLTIP,  this, hoverItem);

        // setting a tooltip upon leaving a view is getting the tooltip displayed
        // on the neighbouring view ...
#ifdef __WXOSX__
        if ( event.Leaving() )
            SetToolTip(nullptr);
        else
#endif
        if ( GetEventHandler()->ProcessEvent(hevent) )
        {
            // If the user permitted the tooltip change, update it, otherwise
            // remove any old tooltip we might have.
            if ( hevent.IsAllowed() )
                SetToolTip(hevent.m_label);
            else
                SetToolTip(nullptr);
        }
    }
#endif

    // we process left mouse up event (enables in-place edit), middle/right down
    // (pass to the user code), left dbl click (activate item) and
    // dragging/moving events for items drag-and-drop
    if ( !(event.LeftDown() ||
           event.LeftUp() ||
           event.MiddleDown() ||
           event.RightDown() ||
           event.LeftDClick() ||
           event.Dragging() ||
           ((event.Moving() || event.RightUp()) && m_isDragging)) )
    {
        event.Skip();

        return;
    }


    flags = 0;
    wxGenericTreeItem *item = m_anchor->HitTest(pt, this, flags, 0);

    if ( event.Dragging() && !m_isDragging )
    {
        if (m_dragCount == 0)
            m_dragStart = pt;

        m_dragCount++;

        if (m_dragCount != 3)
        {
            // wait until user drags a bit further...
            return;
        }

        wxEventType command = event.RightIsDown()
                              ? wxEVT_TREE_BEGIN_RDRAG
                              : wxEVT_TREE_BEGIN_DRAG;

        wxTreeEvent nevent(command,  this, m_current);
        nevent.SetPoint(CalcScrolledPosition(pt));

        // by default the dragging is not supported, the user code must
        // explicitly allow the event for it to take place
        nevent.Veto();

        if ( GetEventHandler()->ProcessEvent(nevent) && nevent.IsAllowed() )
        {
            // we're going to drag this item
            m_isDragging = true;

            // remember the old cursor because we will change it while
            // dragging
            m_oldCursor = m_cursor;

            // in a single selection control, hide the selection temporarily
            if ( !(GetWindowStyleFlag() & wxTR_MULTIPLE) )
            {
                m_oldSelection = GetItemPtr(GetSelection());

                if ( m_oldSelection )
                {
                    m_oldSelection->SetHilight(false);
                    RefreshLine(m_oldSelection);
                }
            }

            CaptureMouse();
        }
    }
    else if ( event.Dragging() )
    {
        if ( item != m_dropTarget )
        {
            // unhighlight the previous drop target
            DrawDropEffect(m_dropTarget);

            m_dropTarget = item;

            // highlight the current drop target if any
            DrawDropEffect(m_dropTarget);

#if defined(__WXMSW__) || defined(__WXMAC__) || defined(__WXGTK__)
            Update();
#else
            // TODO: remove this call or use wxEventLoopBase::GetActive()->YieldFor(wxEVT_CATEGORY_UI)
            //       instead (needs to be tested!)
            wxYieldIfNeeded();
#endif
        }
    }
    else if ( (event.LeftUp() || event.RightUp()) && m_isDragging )
    {
        ReleaseMouse();

        // erase the highlighting
        DrawDropEffect(m_dropTarget);

        if ( m_oldSelection )
        {
            m_oldSelection->SetHilight(true);
            RefreshLine(m_oldSelection);
            m_oldSelection = nullptr;
        }

        // generate the drag end event
        wxTreeEvent eventEndDrag(wxEVT_TREE_END_DRAG,  this, item);

        eventEndDrag.m_pointDrag = CalcScrolledPosition(pt);

        (void)GetEventHandler()->ProcessEvent(eventEndDrag);

        m_isDragging = false;
        m_dropTarget = nullptr;

        SetCursor(m_oldCursor);

#if defined( __WXMSW__ ) || defined(__WXMAC__) || defined(__WXGTK__)
        Update();
#else
        // TODO: remove this call or use wxEventLoopBase::GetActive()->YieldFor(wxEVT_CATEGORY_UI)
        //       instead (needs to be tested!)
        wxYieldIfNeeded();
#endif
    }
    else
    {
        // If we got to this point, we are not dragging or moving the mouse.
        // Because the code in carbon/toplevel.cpp will only set focus to the
        // tree if we skip for EVT_LEFT_DOWN, we MUST skip this event here for
        // focus to work.
        // We skip even if we didn't hit an item because we still should
        // restore focus to the tree control even if we didn't exactly hit an
        // item.
        if ( event.LeftDown() )
        {
            event.Skip();
        }

        // here we process only the messages which happen on tree items

        m_dragCount = 0;

        if ( item == nullptr )
        {
            event.Skip();
            return;
        }

        if ( event.RightDown() )
        {
            // If the item is already selected, do not update the selection.
            // Multi-selections should not be cleared if a selected item is
            // clicked.
            if (!IsSelected(item))
            {
                DoSelectItem(item, true, false);
            }

            wxTreeEvent
                nevent(wxEVT_TREE_ITEM_RIGHT_CLICK,  this, item);
            nevent.m_pointDrag = CalcScrolledPosition(pt);
            event.Skip(!GetEventHandler()->ProcessEvent(nevent));

            // Consistent with MSW (for now), send the ITEM_MENU *after*
            // the RIGHT_CLICK event. TODO: This behaviour may change.
            wxTreeEvent nevent2(wxEVT_TREE_ITEM_MENU,  this, item);
            nevent2.m_pointDrag = CalcScrolledPosition(pt);
            GetEventHandler()->ProcessEvent(nevent2);
        }
        else if ( event.MiddleDown() )
        {
            wxTreeEvent
                nevent(wxEVT_TREE_ITEM_MIDDLE_CLICK,  this, item);
            nevent.m_pointDrag = CalcScrolledPosition(pt);
            event.Skip(!GetEventHandler()->ProcessEvent(nevent));
        }
        else if ( event.LeftUp() )
        {
            if (flags & wxTREE_HITTEST_ONITEMSTATEICON)
            {
                wxTreeEvent
                    nevent(wxEVT_TREE_STATE_IMAGE_CLICK, this, item);
                GetEventHandler()->ProcessEvent(nevent);
            }

            bool canStartRenameTimer = true;

            // Don't deselect anything if we're just collapsing or expanding
            // the item.
            if ( !(flags & wxTREE_HITTEST_ONITEMBUTTON) )
            {
                // this facilitates multiple-item drag-and-drop
                if ( HasFlag(wxTR_MULTIPLE) &&
                        !(event.CmdDown() || event.ShiftDown()) )
                {
                    wxArrayTreeItemIds selections;
                    if ( GetSelections(selections) > 1 )
                    {
                        // For compatibility with wxMSW.
                        // We need to block editing if the item is part of a multiple selection,
                        // because wxMSW only deselects the other items without starting editing
                        // the selected item.
                        canStartRenameTimer = false;

                        DoSelectItem(item, true, false);
                    }
                }
            }

            if ( m_lastOnSame )
            {
                if ( (item == m_current) &&
                     (flags & wxTREE_HITTEST_ONITEMLABEL) &&
                     HasFlag(wxTR_EDIT_LABELS) )
                {
                    if ( m_renameTimer )
                    {
                        if ( m_renameTimer->IsRunning() )
                            m_renameTimer->Stop();
                    }
                    else
                    {
                        m_renameTimer = new wxTreeRenameTimer( this );
                    }

                    if ( canStartRenameTimer )
                    {
                        m_renameTimer->Start( wxTreeRenameTimer::DELAY, true );
                    }
                }

                m_lastOnSame = false;
            }
        }
        else // !RightDown() && !MiddleDown() && !LeftUp()
        {
            // ==> LeftDown() || LeftDClick()
            if ( event.LeftDown() )
            {
                // If we click on an already selected item but do it to return
                // the focus to the control, it shouldn't start editing the
                // item label because it's too easy to start editing
                // accidentally (and also because nobody else does it like
                // this). So only set this flag, used to decide whether we
                // should start editing the label later, if we already have
                // focus.
                m_lastOnSame = item == m_current && HasFocus();
            }

            if ( flags & wxTREE_HITTEST_ONITEMBUTTON )
            {
                // toggle the item for both single clicks and double clicks
                if ( event.LeftDown() || event.LeftDClick() )
                {
                    Toggle( item );
                }

                // don't select the item if the button was clicked
                return;
            }


            // clear the previously selected items, if the
            // user clicked outside of the present selection.
            // otherwise, perform the deselection on mouse-up.
            // this allows multiple drag and drop to work.
            // but if Cmd is down, toggle selection of the clicked item
            if (!IsSelected(item) || event.CmdDown())
            {
                // how should the selection work for this event?
                bool is_multiple, extended_select, unselect_others;
                EventFlagsToSelType(GetWindowStyleFlag(),
                                    event.ShiftDown(),
                                    event.CmdDown(),
                                    is_multiple,
                                    extended_select,
                                    unselect_others);

                DoSelectItem(item, unselect_others, extended_select);
            }


            // For some reason, Windows isn't recognizing a left double-click,
            // so we need to simulate it here.  Allow 200 milliseconds for now.
            if ( event.LeftDClick() )
            {
                // double clicking should not start editing the item label
                if ( m_renameTimer )
                    m_renameTimer->Stop();

                m_lastOnSame = false;

                // send activate event first
                wxTreeEvent
                    nevent(wxEVT_TREE_ITEM_ACTIVATED,  this, item);
                nevent.m_pointDrag = CalcScrolledPosition(pt);
                if ( !GetEventHandler()->ProcessEvent( nevent ) )
                {
                    // if the user code didn't process the activate event,
                    // handle it ourselves by toggling the item when it is
                    // double clicked
                    if ( item->HasPlus() )
                    {
                        Toggle(item);
                    }
                }
            }
        }
    }
}

void wxGenericTreeCtrl::OnInternalIdle()
{
    wxWindow::OnInternalIdle();

    // Check if we need to select the root item
    // because nothing else has been selected.
    // Delaying it means that we can invoke event handlers
    // as required, when a first item is selected.
    if (!HasFlag(wxTR_MULTIPLE) && !GetSelection().IsOk())
    {
        if (m_select_me)
            SelectItem(m_select_me);
        else if (GetRootItem().IsOk())
            SelectItem(GetRootItem());
    }

    // after all changes have been done to the tree control,
    // actually redraw the tree when everything is over
    if (m_dirty)
        DoDirtyProcessing();
}

void
wxGenericTreeCtrl::CalculateLevel(wxGenericTreeItem *item,
                                  wxReadOnlyDC &dc,
                                  int level,
                                  int &y )
{
    int indent = FromDIP(m_indent);
    int spacing = FromDIP(m_spacing);

    int x = level*indent;
    if (!HasFlag(wxTR_HIDE_ROOT))
    {
        x += indent;
    }
    else if (level == 0)
    {
        // a hidden root is not evaluated, but its
        // children are always calculated
        goto Recurse;
    }

    item->CalculateSize(this, dc);

    // set its position
    item->SetX( x+spacing );
    item->SetY( y );
    y += GetLineHeight(item);

    if ( !item->IsExpanded() )
    {
        // we don't need to calculate collapsed branches
        return;
    }

  Recurse:
    wxGenericTreeItems& children = item->GetChildren();
    size_t n, count = children.size();
    ++level;
    for (n = 0; n < count; ++n )
        CalculateLevel( children[n], dc, level, y );  // recurse
}

void wxGenericTreeCtrl::CalculatePositions()
{
    if ( !m_anchor )
        return;

    wxInfoDC dc(this);
    PrepareDC( dc );

    int y = 2;
    CalculateLevel( m_anchor, dc, 0, y ); // start recursion
}

void wxGenericTreeCtrl::Refresh(bool eraseBackground, const wxRect *rect)
{
    if ( !IsFrozen() )
        wxTreeCtrlBase::Refresh(eraseBackground, rect);
}

void wxGenericTreeCtrl::RefreshSubtree(wxGenericTreeItem *item)
{
    if (m_dirty || IsFrozen() )
        return;

    wxSize client = GetClientSize();

    wxRect rect;
    CalcScrolledPosition(0, item->GetY(), nullptr, &rect.y);
    rect.width = client.x;
    rect.height = client.y;

    Refresh(true, &rect);

    AdjustMyScrollbars();
}

void wxGenericTreeCtrl::RefreshLine( wxGenericTreeItem *item )
{
    if (m_dirty || IsFrozen() )
        return;

    wxRect rect;
    CalcScrolledPosition(0, item->GetY(), nullptr, &rect.y);
    rect.width = GetClientSize().x;
    rect.height = GetLineHeight(item); //dc.GetCharHeight() + 6;

    Refresh(true, &rect);
}

void wxGenericTreeCtrl::RefreshSelected()
{
    if (IsFrozen())
        return;

    // TODO: this is awfully inefficient, we should keep the list of all
    //       selected items internally, should be much faster
    if ( m_anchor )
        RefreshSelectedUnder(m_anchor);
}

void wxGenericTreeCtrl::RefreshSelectedUnder(wxGenericTreeItem *item)
{
    if (IsFrozen())
        return;

    if ( item->IsSelected() )
        RefreshLine(item);

    const wxGenericTreeItems& children = item->GetChildren();
    size_t count = children.size();
    for ( size_t n = 0; n < count; n++ )
    {
        RefreshSelectedUnder(children[n]);
    }
}

void wxGenericTreeCtrl::DoThaw()
{
    wxTreeCtrlBase::DoThaw();

    if ( m_dirty )
        DoDirtyProcessing();
    else
        Refresh();
}

// ----------------------------------------------------------------------------
// changing colours: we need to refresh the tree control
// ----------------------------------------------------------------------------

bool wxGenericTreeCtrl::SetBackgroundColour(const wxColour& colour)
{
    if ( !wxWindow::SetBackgroundColour(colour) )
        return false;

    m_hasExplicitBgCol = true;

    Refresh();

    return true;
}

bool wxGenericTreeCtrl::SetForegroundColour(const wxColour& colour)
{
    if ( !wxWindow::SetForegroundColour(colour) )
        return false;

    m_hasExplicitFgCol = true;

    Refresh();

    return true;
}

void wxGenericTreeCtrl::OnGetToolTip( wxTreeEvent &event )
{
#if wxUSE_TOOLTIPS
    wxTreeItemId itemId = event.GetItem();
    const wxGenericTreeItem* const pItem = GetItemPtr(itemId);

    // Check if the item fits into the client area:
    if ( pItem->GetX() + pItem->GetWidth() > GetClientSize().x )
    {
        // If it doesn't, show its full text in the tooltip.
        event.SetLabel(pItem->GetText());
    }
    else
#endif // wxUSE_TOOLTIPS
    {
        // veto processing the event, nixing any tooltip
        event.Veto();
    }
}


// NOTE: If using the wxListBox visual attributes works everywhere then this can
// be removed, as well as the #else case below.
#define _USE_VISATTR 0

//static
wxVisualAttributes
#if _USE_VISATTR
wxGenericTreeCtrl::GetClassDefaultAttributes(wxWindowVariant variant)
#else
wxGenericTreeCtrl::GetClassDefaultAttributes(wxWindowVariant WXUNUSED(variant))
#endif
{
#if _USE_VISATTR
    // Use the same color scheme as wxListBox
    return wxListBox::GetClassDefaultAttributes(variant);
#else
    wxVisualAttributes attr;
    attr.colFg = wxSystemSettings::GetColour(wxSYS_COLOUR_LISTBOXTEXT);
    attr.colBg = wxSystemSettings::GetColour(wxSYS_COLOUR_LISTBOX);
#if defined(__WXOSX__)
    attr.font = wxFont(wxOSX_SYSTEM_FONT_VIEWS);
#else
    attr.font = wxSystemSettings::GetFont(wxSYS_DEFAULT_GUI_FONT);
#endif
    return attr;
#endif
}

void wxGenericTreeCtrl::DoDirtyProcessing()
{
    if (IsFrozen())
        return;

    m_dirty = false;

    CalculatePositions();
    Refresh();
    AdjustMyScrollbars();
}

wxSize wxGenericTreeCtrl::DoGetBestSize() const
{
    // make sure all positions are calculated as normally this only done during
    // idle time but we need them for base class DoGetBestSize() to return the
    // correct result
    wxConstCast(this, wxGenericTreeCtrl)->CalculatePositions();

    wxSize size = wxTreeCtrlBase::DoGetBestSize();

    // there seems to be an implicit extra border around the items, although
    // I'm not really sure where does it come from -- but without this, the
    // scrollbars appear in a tree with default/best size
    size.IncBy(4, 4);

    // and the border has to be rounded up to a multiple of PIXELS_PER_UNIT or
    // scrollbars still appear
    const wxSize& borderSize = GetWindowBorderSize();

    int dx = (size.x - borderSize.x) % PIXELS_PER_UNIT;
    if ( dx )
        size.x += PIXELS_PER_UNIT - dx;
    int dy = (size.y - borderSize.y) % PIXELS_PER_UNIT;
    if ( dy )
        size.y += PIXELS_PER_UNIT - dy;

    return size;
}

#endif // wxUSE_TREECTRL
