Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Using BeginCombo() and avanced: custom preview, filtering #1658

Open
ocornut opened this issue Mar 3, 2018 · 38 comments
Open

Using BeginCombo() and avanced: custom preview, filtering #1658

ocornut opened this issue Mar 3, 2018 · 38 comments

Comments

@ocornut
Copy link
Owner

ocornut commented Mar 3, 2018

I feel like this is one of the small/nice feature that may have passed under the radar so I'm going to write a small blurb about it here.

There's a BeginCombo/EndCombo() api which is much more flexible that the "old" Combo() function.

bool BeginCombo(const char* label, const char* preview_value, ImGuiComboFlags flags = 0);
void EndCombo(); // only call EndCombo() if BeginCombo() returns true!

Basically with this api you can control the way you store your current selection and item storage (they don't have to be stored sequentially and randomly accessible, so if your natural "selection" data is a pointer you can use that, you can submit filtered lists easily, etc.

const char* items[] = { "AAAA", "BBBB", "CCCC", "DDDD", "EEEE", "FFFF", "GGGG", "HHHH", "IIII", "JJJJ", "KKKK", "LLLLLLL", "MMMM", "OOOOOOO", "PPPP", "QQQQQQQQQQ", "RRR", "SSSS" };
static const char* current_item = NULL;

if (ImGui::BeginCombo("##combo", current_item)) // The second parameter is the label previewed before opening the combo.
{
    for (int n = 0; n < IM_ARRAYSIZE(items); n++)
    {
        bool is_selected = (current_item == items[n]); // You can store your selection however you want, outside or inside your objects
        if (ImGui::Selectable(items[n], is_selected)
            current_item = items[n];
        if (is_selected)
            ImGui::SetItemDefaultFocus();   // You may set the initial focus when opening the combo (scrolling + for keyboard navigation support)
    }
    ImGui::EndCombo();
}

You can easily build combo boxes for your custom types using this.

Today I asked extra flags:
ImGuiComboFlags_NoArrowButton

image

ImGuiComboFlags_NoPreview

image

You could previously achieve this by pushing an item width the width of the button only, but it's not doable with just a flag.

ImGuiComboFlags_NoPreview + hidden label:

image

Also consider creating custom layout like:

const char* items[] = { "AAAA", "BBBB", "CCCC", "DDDD", "EEEE", "FFFF", "GGGG", "HHHH", "IIII", "JJJJ", "KKKK", "LLLLLLL", "MMMM", "OOOOOOO", "PPPP", "QQQQQQQQQQ", "RRR", "SSSS" };
static const char* current_item = NULL;
ImGuiComboFlags flags = ImGuiComboFlags_NoArrowButton;

ImGuiStyle& style = ImGui::GetStyle();
float w = ImGui::CalcItemWidth();
float spacing = style.ItemInnerSpacing.x;
float button_sz = ImGui::GetFrameHeight();
ImGui::PushItemWidth(w - spacing * 2.0f - button_sz * 2.0f);
if (ImGui::BeginCombo("##custom combo", current_item, ImGuiComboFlags_NoArrowButton))
{
    for (int n = 0; n < IM_ARRAYSIZE(items); n++)
    {
        bool is_selected = (current_item == items[n]);
        if (ImGui::Selectable(items[n], is_selected))
            current_item = items[n];
        if (is_selected)
            ImGui::SetItemDefaultFocus();
    }
    ImGui::EndCombo();
}
ImGui::PopItemWidth();
ImGui::SameLine(0, spacing);
if (ImGui::ArrowButton("##r", ImGuiDir_Left))
{
}
ImGui::SameLine(0, spacing);
if (ImGui::ArrowButton("##r", ImGuiDir_Right))
{
}
ImGui::SameLine(0, style.ItemInnerSpacing.x);
ImGui::Text("Custom Combo");

image

Clicking the preview area will get you the normal combo popup, etc.

@jdumas
Copy link
Contributor

jdumas commented Mar 15, 2018

Hi,

Nice example!
Is it possible to add an image before the label in the selection list, or in the selected choice?

@ocornut
Copy link
Owner Author

ocornut commented Mar 15, 2018

Yes, they are regular popup so you can do anything within them.

@jdumas
Copy link
Contributor

jdumas commented Mar 15, 2018

I managed to display an image per item by calling a ImGui::Selectable("", is_selected);, followed by ImGui::SameLine(); and then showing image + text:

cmap

However, I cannot figure out how to show the picture of the colormap inside the frame that shows the selected one.

EDIT: Well ok what I did doesn't really work actually. If I set the selectable size to "" then I cannot click on the image or the text to change the selected value ... I'm sure it's possible to fix this with the current API, but I haven't figure out yet how.

@ocornut
Copy link
Owner Author

ocornut commented Mar 16, 2018

EDIT: Well ok what I did doesn't really work actually. If I set the selectable size to "" then I cannot click on the image or the text to change the selected value ... I'm sure it's possible to fix this with the current API, but I haven't figure out yet how.

If you set the selectable label to "" make sure there is a PushID() or use "##someid" else all your selectable are using the same identifier and will conflict.
Selectable("") + SameLine + Image + SameLine + Text should work.

However, I cannot figure out how to show the picture of the colormap inside the frame that shows the selected one.

That's a trickier one unfortunately, thought you can draw inside the combo widget:

ImVec2 combo_pos = ImGui::GetCursorScreenPos();
if (ImGui::BeginCombo(label, ""))
{
     [...]
    ImGui::EndCombo();
}
[...]
ImVec2 backup_pos = ImGui::GetCursorScreenPos();
ImGuiStyle& style = ImGui::GetStyle();
ImGui::SetCursorScreenPos(ImVec2(combo_pos.x + style.FramePadding.x, combo_pos.y));
ImGui::ColorButton("blah", ImVec4(1,0,0,1));
ImGui::SameLine();
ImGui::Text("Hello");
ImGui::SetCursorScreenPos(backup_pos);

image

But you will run into clipping issues (only you push a clipping rectangle or use internal functions that draw clipped text). Maybe this pattern could be formalized into something better.

I think you would be better off using Image + SameLine + Combo with a manipulation of item width.

@jdumas
Copy link
Contributor

jdumas commented Mar 16, 2018

Right now my window has a fixed size, and the text fit in the box, so what you suggest may just work (™). Thanks for the tip! It works indeed better with the PushID() :p

While I'm at it, what is the correct way to calculate the size of the button? I am using ImGui::GetStyle().FrameRounding = 2.0f; and ImGui::GetStyle().FrameBorderSize = 1.0f;, and I am positioning my text and positions as so:

ImGui::SetCursorScreenPos(ImVec2(combo_pos.x + style.FramePadding.x, combo_pos.y + style.FramePadding.y));
float h = ImGui::GetTextLineHeightWithSpacing() - style.FramePadding.y;
ImGui::Image(tex_id, ImVec2(h, h);
ImGui::SameLine();
ImGui::Text("Viridis");

padding

The image seems a bit too big and the padding is not even on top and bottom, so I may have been doing the calculation wrong.

@ocornut
Copy link
Owner Author

ocornut commented Mar 16, 2018

While I'm at it, what is the correct way to calculate the size of the button?

Neither FrameRounding or FrameBorderSize after the size of elements (the border size is taken "inside" the item). The size of a button is typically size of text + FramePadding * 2.

float h = ImGui::GetTextLineHeightWithSpacing() - style.FramePadding.y;

Here you probably want to just float h = ImGui::GetTextLineHeight().

@jdumas
Copy link
Contributor

jdumas commented Mar 16, 2018

You are right of course =). GetTextLineHeight() works just fine here. Thanks!

@r-lyeh
Copy link

r-lyeh commented Oct 5, 2018

Hey,

I am browsing closed issues and cannot find any reference to create a filtered combo.

What's the best current option to create a FilterCombo widget as seen in UE4/Sublime/etc?
Ie, some kind of Input filter on top then a filtered combo list below.

Ty!

PS: The pic below uses fuzzy pattern matching rather than simple filtering, but you get the idea.

image

@ocornut ocornut added the popups label Oct 5, 2018
@ocornut
Copy link
Owner Author

ocornut commented Oct 5, 2018

I don't have a good answer for you, for not having tried to make an interactive one, but #718 is the thread to check to fish for ideas.

@r-lyeh
Copy link

r-lyeh commented Oct 5, 2018

Ah kewl :)

I've started from your snippet in #718 and started to mess with it to add interactivity + basic fuzzy search. It could be 1,000 times better but works for me now :D

// imgui combo filter v1.0, by @r-lyeh (public domain)
// contains code by @harold-b (public domain?)

/*  Demo: */
/*
    {
        // requisite: hints must be alphabetically sorted beforehand
        const char *hints[] = {
            "AnimGraphNode_CopyBone",
            "ce skipaa",
            "ce skipscreen",
            "ce skipsplash",
            "ce skipsplashscreen",
            "client_unit.cpp",
            "letrograd",
            "level",
            "leveler",
            "MacroCallback.cpp",
            "Miskatonic university",
            "MockAI.h",
            "MockGameplayTasks.h",
            "MovieSceneColorTrack.cpp",
            "r.maxfps",
            "r.maxsteadyfps",
            "reboot",
            "rescale",
            "reset",
            "resource",
            "restart",
            "retrocomputer",
            "retrograd",
            "return",
            "slomo 10",
            "SVisualLoggerLogsList.h",
            "The Black Knight",
        };
        static ComboFilterState s = {0};
        static char buf[128] = "type text here...";
        if( ComboFilter("my combofilter", buf, IM_ARRAYSIZE(buf), hints, IM_ARRAYSIZE(hints), s) ) {
            puts( buf );
        }
    }
*/

#pragma once

struct ComboFilterState
{
    int  activeIdx;         // Index of currently 'active' item by use of up/down keys
    bool selectionChanged;  // Flag to help focus the correct item when selecting active item
};

static bool ComboFilter__DrawPopup( ComboFilterState& state, int START, const char **ENTRIES, int ENTRY_COUNT )
{
    using namespace ImGui;
    bool clicked = 0;

    // Grab the position for the popup
    ImVec2 pos = GetItemRectMin(); pos.y += GetItemRectSize().y;
    ImVec2 size = ImVec2( GetItemRectSize().x-60, GetItemsLineHeightWithSpacing() * 4 );

    PushStyleVar( ImGuiStyleVar_WindowRounding, 0 );

    ImGuiWindowFlags flags = 
        ImGuiWindowFlags_NoTitleBar          | 
        ImGuiWindowFlags_NoResize            |
        ImGuiWindowFlags_NoMove              |
        ImGuiWindowFlags_HorizontalScrollbar |
        ImGuiWindowFlags_NoSavedSettings     |
        0; //ImGuiWindowFlags_ShowBorders;

    SetNextWindowFocus();

    SetNextWindowPos ( pos );
    SetNextWindowSize( size );
    Begin("##combo_filter", nullptr, flags );

    PushAllowKeyboardFocus( false );

    for( int i = 0; i < ENTRY_COUNT; i++ ) {
        // Track if we're drawing the active index so we
        // can scroll to it if it has changed
        bool isIndexActive = state.activeIdx == i;

        if( isIndexActive ) {
            // Draw the currently 'active' item differently
            // ( used appropriate colors for your own style )
            PushStyleColor( ImGuiCol_Border, ImVec4( 1, 1, 0, 1 ) );
        }

        PushID( i );
        if( Selectable( ENTRIES[i], isIndexActive ) ) {
            // And item was clicked, notify the input
            // callback so that it can modify the input buffer
            state.activeIdx = i;
            clicked = 1;
        }
        if( IsItemFocused() && IsKeyPressed(GetIO().KeyMap[ImGuiKey_Enter]) ) {
            // Allow ENTER key to select current highlighted item (w/ keyboard navigation)
            state.activeIdx = i;
            clicked = 1;
        }
        PopID();

        if( isIndexActive ) {
            if( state.selectionChanged ) {
                // Make sure we bring the currently 'active' item into view.
                SetScrollHere();
                state.selectionChanged = false;
            }

            PopStyleColor(1);
        }
    }

    PopAllowKeyboardFocus();
    End();
    PopStyleVar(1);

    return clicked;
}

static bool ComboFilter( const char *id, char *buffer, int bufferlen, const char **hints, int num_hints, ComboFilterState &s ) {
    struct fuzzy {
        static int score( const char *str1, const char *str2 ) {
            int score = 0, consecutive = 0, maxerrors = 0;
            while( *str1 && *str2 ) {
                int is_leading = (*str1 & 64) && !(str1[1] & 64);
                if( (*str1 & ~32) == (*str2 & ~32) ) {
                    int had_separator = (str1[-1] <= 32);
                    int x = had_separator || is_leading ? 10 : consecutive * 5;
                    consecutive = 1;
                    score += x;
                    ++str2;
                } else {
                    int x = -1, y = is_leading * -3;
                    consecutive = 0;
                    score += x;
                    maxerrors += y;
                }
                ++str1;
            }
            return score + (maxerrors < -9 ? -9 : maxerrors);
        }
        static int search( const char *str, int num, const char *words[] ) {
            int scoremax = 0;
            int best = -1;
            for( int i = 0; i < num; ++i ) {
                int score = fuzzy::score( words[i], str );
                int record = ( score >= scoremax );
                int draw = ( score == scoremax );
                if( record ) {
                    scoremax = score;
                    if( !draw ) best = i;
                    else best = best >= 0 && strlen(words[best]) < strlen(words[i]) ? best : i;
                }
            }
            return best;
        }
    };
    using namespace ImGui;
    bool done = InputText(id, buffer, bufferlen, ImGuiInputTextFlags_AutoSelectAll | ImGuiInputTextFlags_EnterReturnsTrue );
    bool hot = s.activeIdx >= 0 && strcmp(buffer, hints[s.activeIdx]);
    if( hot ) {
        int new_idx = fuzzy::search( buffer, num_hints, hints );
        int idx = new_idx >= 0 ? new_idx : s.activeIdx;
        s.selectionChanged = s.activeIdx != idx;
        s.activeIdx = idx;
        if( done || ComboFilter__DrawPopup( s, idx, hints, num_hints ) ) {
            int i = s.activeIdx;
            if( i >= 0 ) {
                strcpy(buffer, hints[i]);
                done = true;
            }
        }
    }
    return done;
}

PS: sorry no gifs today!

EDIT: updated code to v1.0

@r-lyeh
Copy link

r-lyeh commented Oct 15, 2018

I've updated the snippet above to a cleaner implementation.
Also, here's latest gif anim (showcasing mouse & keyboardnav picking):

gif

@ocornut
Copy link
Owner Author

ocornut commented Oct 16, 2018

Thanks @r-lyeh for the code and gif, this is really nice!

@r-lyeh
Copy link

r-lyeh commented Oct 17, 2018

I just stumbled upon how FlatUI handles the combo filtering, and its logic fits better with IMGUI mentality IMO.

I will try to put the filter inside the combo popup (and leave the header to behave exactly like current Combo). Will create a new snippet someday.

image

flat-ui demo: http://designmodo.github.io/Flat-UI/

@kovewnikov
Copy link

kovewnikov commented Mar 16, 2020

Hello guys, check out my solution over this problem. I have taken approach @r-lyeh about fuzzy search and tried to create total combo-like widget

/*  Demo: */
/*
const char *hints[] = {
                "AnimGraphNode_CopyBone",
                "ce skipaa",
                "ce skipscreen",
                "ce skipsplash",
                "ce skipsplashscreen",
                "client_unit.cpp",
                "letrograd",
                "level",
                "leveler",
                "MacroCallback.cpp",
                "Miskatonic university",
                "MockAI.h",
                "MockGameplayTasks.h",
                "MovieSceneColorTrack.cpp",
                "r.maxfps",
                "r.maxsteadyfps",
                "reboot",
                "rescale",
                "reset",
                "resource",
                "restart",
                "retrocomputer",
                "retrograd",
                "return",
                "slomo 10",
                "SVisualLoggerLogsList.h",
                "The Black Knight",
            };
            static ComboFilterState s = {0, false};
            static char buf[128];
            static bool once = false;
            if(!once) {
                memcpy(buf, hints[0], strlen(hints[0]) + 1);
                once = true;
            }
            
            if( ComboFilter("my combofilter", buf, IM_ARRAYSIZE(buf), hints, IM_ARRAYSIZE(hints), s) ) {
                //...picking was occured
            }
*/

#pragma once

struct ComboFilterState {
    int  activeIdx;
    bool selectionChanged;
};

bool ComboFilter(const char *label, char *buffer, int bufferlen, const char **hints, int num_hints, ComboFilterState &s, ImGuiComboFlags flags = 0) {
    
    using namespace ImGui;
        
    s.selectionChanged = false;
    
    // Always consume the SetNextWindowSizeConstraint() call in our early return paths
    ImGuiContext& g = *GImGui;

    ImGuiWindow* window = GetCurrentWindow();
    if (window->SkipItems)
        return false;
    
    const ImGuiID id = window->GetID(label);
    bool popup_open = IsPopupOpen(id);
    bool popupNeedBeOpen = strcmp(buffer, hints[s.activeIdx]);
    bool popupJustOpened = false;
    
    IM_ASSERT((flags & (ImGuiComboFlags_NoArrowButton | ImGuiComboFlags_NoPreview)) != (ImGuiComboFlags_NoArrowButton | ImGuiComboFlags_NoPreview)); // Can't use both flags together

    const ImGuiStyle& style = g.Style;
    
    const float arrow_size = (flags & ImGuiComboFlags_NoArrowButton) ? 0.0f : GetFrameHeight();
    const ImVec2 label_size = CalcTextSize(label, NULL, true);
    const float expected_w = CalcItemWidth();
    const float w = (flags & ImGuiComboFlags_NoPreview) ? arrow_size : expected_w;
    const ImRect frame_bb(window->DC.CursorPos, ImVec2(window->DC.CursorPos.x + w, window->DC.CursorPos.y + label_size.y + style.FramePadding.y*2.0f));
    const ImRect total_bb(frame_bb.Min, ImVec2((label_size.x > 0.0f ? style.ItemInnerSpacing.x + label_size.x : 0.0f) + frame_bb.Max.x, frame_bb.Max.y));
    const float value_x2 = ImMax(frame_bb.Min.x, frame_bb.Max.x - arrow_size);
    ItemSize(total_bb, style.FramePadding.y);
    if (!ItemAdd(total_bb, id, &frame_bb))
        return false;
    
    
    bool hovered, held;
    bool pressed = ButtonBehavior(frame_bb, id, &hovered, &held);
    
    if(!popup_open) {
        const ImU32 frame_col = GetColorU32(hovered ? ImGuiCol_FrameBgHovered : ImGuiCol_FrameBg);
        RenderNavHighlight(frame_bb, id);
        if (!(flags & ImGuiComboFlags_NoPreview))
            window->DrawList->AddRectFilled(frame_bb.Min, ImVec2(value_x2, frame_bb.Max.y), frame_col, style.FrameRounding, (flags & ImGuiComboFlags_NoArrowButton) ? ImDrawCornerFlags_All : ImDrawCornerFlags_Left);
    }
    if (!(flags & ImGuiComboFlags_NoArrowButton))
    {
        ImU32 bg_col = GetColorU32((popup_open || hovered) ? ImGuiCol_ButtonHovered : ImGuiCol_Button);
        ImU32 text_col = GetColorU32(ImGuiCol_Text);
        window->DrawList->AddRectFilled(ImVec2(value_x2, frame_bb.Min.y), frame_bb.Max, bg_col, style.FrameRounding, (w <= arrow_size) ? ImDrawCornerFlags_All : ImDrawCornerFlags_Right);
        if (value_x2 + arrow_size - style.FramePadding.x <= frame_bb.Max.x)
            RenderArrow(window->DrawList, ImVec2(value_x2 + style.FramePadding.y, frame_bb.Min.y + style.FramePadding.y), text_col, ImGuiDir_Down, 1.0f);
    }
    if(!popup_open) {

        RenderFrameBorder(frame_bb.Min, frame_bb.Max, style.FrameRounding);
        if (buffer != NULL && !(flags & ImGuiComboFlags_NoPreview))
            
            RenderTextClipped(ImVec2(frame_bb.Min.x + style.FramePadding.x, frame_bb.Min.y + style.FramePadding.y), ImVec2(value_x2, frame_bb.Max.y), buffer, NULL, NULL, ImVec2(0.0f,0.0f));

        if ((pressed || g.NavActivateId == id || popupNeedBeOpen) && !popup_open)
        {
            if (window->DC.NavLayerCurrent == 0)
                window->NavLastIds[0] = id;
            OpenPopupEx(id);
            popup_open = true;
            popupJustOpened = true;
        }
    }
    
    if (label_size.x > 0)
    RenderText(ImVec2(frame_bb.Max.x + style.ItemInnerSpacing.x, frame_bb.Min.y + style.FramePadding.y), label);
    
    if (!popup_open) {
        return false;
    }
    
    const float totalWMinusArrow = w - arrow_size;
    struct ImGuiSizeCallbackWrapper {
        static void sizeCallback(ImGuiSizeCallbackData* data)
        {
            float* totalWMinusArrow = (float*)(data->UserData);
            data->DesiredSize = ImVec2(*totalWMinusArrow, 200.f);
        }
    };
    SetNextWindowSizeConstraints(ImVec2(0 ,0), ImVec2(totalWMinusArrow, 150.f), ImGuiSizeCallbackWrapper::sizeCallback, (void*)&totalWMinusArrow);

    char name[16];
    ImFormatString(name, IM_ARRAYSIZE(name), "##Combo_%02d", g.BeginPopupStack.Size); // Recycle windows based on depth

    // Peak into expected window size so we can position it
    if (ImGuiWindow* popup_window = FindWindowByName(name))
        if (popup_window->WasActive)
        {
            ImVec2 size_expected = CalcWindowExpectedSize(popup_window);
            if (flags & ImGuiComboFlags_PopupAlignLeft)
                popup_window->AutoPosLastDirection = ImGuiDir_Left;
            ImRect r_outer = GetWindowAllowedExtentRect(popup_window);
            ImVec2 pos = FindBestWindowPosForPopupEx(frame_bb.GetBL(), size_expected, &popup_window->AutoPosLastDirection, r_outer, frame_bb, ImGuiPopupPositionPolicy_ComboBox);
            
            pos.y -= label_size.y + style.FramePadding.y*2.0f;
            
            SetNextWindowPos(pos);
        }

    // Horizontally align ourselves with the framed text
    ImGuiWindowFlags window_flags = ImGuiWindowFlags_AlwaysAutoResize | ImGuiWindowFlags_Popup | ImGuiWindowFlags_NoTitleBar | ImGuiWindowFlags_NoResize | ImGuiWindowFlags_NoSavedSettings;
//    PushStyleVar(ImGuiStyleVar_WindowPadding, ImVec2(style.FramePadding.x, style.WindowPadding.y));
    bool ret = Begin(name, NULL, window_flags);

    ImGui::PushItemWidth(ImGui::GetWindowWidth());
    ImGui::SetCursorPos(ImVec2(0.f, window->DC.CurrLineTextBaseOffset));
    if(popupJustOpened) {
        ImGui::SetKeyboardFocusHere(0);
    }
    bool done = InputTextEx("", NULL, buffer, bufferlen, ImVec2(0, 0), ImGuiInputTextFlags_AutoSelectAll | ImGuiInputTextFlags_EnterReturnsTrue, NULL, NULL);
    ImGui::PopItemWidth();

    if(s.activeIdx < 0) {
        IM_ASSERT(false); //Undefined behaviour
        return false;
    }
    
    
    if (!ret)
    {
        ImGui::EndChild();
        ImGui::PopItemWidth();
        EndPopup();
        IM_ASSERT(0);   // This should never happen as we tested for IsPopupOpen() above
        return false;
    }
    
    
    ImGuiWindowFlags window_flags2 =  0; //ImGuiWindowFlags_HorizontalScrollbar
    ImGui::BeginChild("ChildL", ImVec2(ImGui::GetContentRegionAvail().x, ImGui::GetContentRegionAvail().y), false, window_flags2);
    
    
    
    
    struct fuzzy {
        static int score( const char *str1, const char *str2 ) {
            int score = 0, consecutive = 0, maxerrors = 0;
            while( *str1 && *str2 ) {
                int is_leading = (*str1 & 64) && !(str1[1] & 64);
                if( (*str1 & ~32) == (*str2 & ~32) ) {
                    int had_separator = (str1[-1] <= 32);
                    int x = had_separator || is_leading ? 10 : consecutive * 5;
                    consecutive = 1;
                    score += x;
                    ++str2;
                } else {
                    int x = -1, y = is_leading * -3;
                    consecutive = 0;
                    score += x;
                    maxerrors += y;
                }
                ++str1;
            }
            return score + (maxerrors < -9 ? -9 : maxerrors);
        }
        static int search( const char *str, int num, const char *words[] ) {
            int scoremax = 0;
            int best = -1;
            for( int i = 0; i < num; ++i ) {
                int score = fuzzy::score( words[i], str );
                int record = ( score >= scoremax );
                int draw = ( score == scoremax );
                if( record ) {
                    scoremax = score;
                    if( !draw ) best = i;
                    else best = best >= 0 && strlen(words[best]) < strlen(words[i]) ? best : i;
                }
            }
            return best;
        }
    };
    
    int new_idx = fuzzy::search( buffer, num_hints, hints );
    int idx = new_idx >= 0 ? new_idx : s.activeIdx;
    s.selectionChanged = s.activeIdx != idx;
    bool selectionChangedLocal = s.selectionChanged;
    s.activeIdx = idx;
    
    if(done) {
        CloseCurrentPopup();
    }
    for (int n = 0; n < num_hints; n++) {;
        bool is_selected = n == s.activeIdx;
        if (is_selected && (IsWindowAppearing() || selectionChangedLocal)) {
             SetScrollHereY();
//            ImGui::SetItemDefaultFocus();
        }
        if (ImGui::Selectable(hints[n], is_selected)) {
            s.selectionChanged = s.activeIdx != n;
            s.activeIdx = n;
            strcpy(buffer, hints[n]);
            CloseCurrentPopup();
        }
    }
    ImGui::EndChild();
    EndPopup();

    return s.selectionChanged && !strcmp(hints[s.activeIdx], buffer);
}

Keep in mind that you need to keep hints list sorted

ezgif com-video-to-gif

@r-lyeh
Copy link

r-lyeh commented Mar 16, 2020

missing a pic!

@kovewnikov
Copy link

missing a pic!

Done

@erwincoumans
Copy link
Contributor

erwincoumans commented Jan 31, 2021

Using this thread and drawImage seems to work, thanks all!

notes

  float button_sz = ImGui::GetFrameHeight();
                        if(ImGui::BeginCombo("##custom combo",current_item,ImGuiComboFlags_NoArrowButton))
                        {
                            for(int n = 0; n < IM_ARRAYSIZE(items); n++)
                            {
                                bool is_selected = (current_item == items[n]);
                                auto drawList = ImGui::GetWindowDrawList();
                                if(ImGui::Selectable(items[n],is_selected))
                                {
                                    selected_item_index = n;
                                    current_item = items[n];
                                }
                                auto rect_min = ImGui::GetItemRectMin();
                                auto rect_max = ImGui::GetItemRectMax();
                                rect_max.x = rect_min.x + 32;
                                drawList->AddImage(ImGui_GetOpenGLTexture(s_noteIcons[n]),rect_min,rect_max,ImVec2(0,0),ImVec2(1,1),IM_COL32(255,255,255,255));
                                if(is_selected)
                                    ImGui::SetItemDefaultFocus();
                            }
                            ImGui::EndCombo();
                        }
                        else
                        {
                            auto rect_min = ImGui::GetItemRectMin();
                            auto rect_max = ImGui::GetItemRectMax();
                            rect_max.x = rect_min.x + 32;
                            auto drawList = ImGui::GetWindowDrawList();
                            drawList->AddImage(ImGui_GetOpenGLTexture(s_noteIcons[selected_item_index]),rect_min,rect_max,ImVec2(0,0),ImVec2(1,1),IM_COL32(255,255,255,255));
                        }

@Nuxar1
Copy link

Nuxar1 commented Feb 7, 2021

const char* items[] = { "AAAA", "BBBB", "CCCC", "DDDD", "EEEE", "FFFF", "GGGG", "HHHH", "IIII", "JJJJ", "KKKK", "LLLLLLL", "MMMM", "OOOOOOO", "PPPP", "QQQQQQQQQQ", "RRR", "SSSS" };
static const char* current_item = NULL;

if (ImGui::BeginCombo("##combo", current_item)) // The second parameter is the label previewed before opening the combo.
{
    for (int n = 0; n < IM_ARRAYSIZE(items); n++)
    {
        bool is_selected = (current_item == items[n]); // You can store your selection however you want, outside or inside your objects
        if (ImGui::Selectable(items[n], is_selected)
            current_item = items[n];
        if (is_selected)
            ImGui::SetItemDefaultFocus();   // You may set the initial focus when opening the combo (scrolling + for keyboard navigation support)
    }
    ImGui::EndCombo();
}

Just letting you know. You're missing a ) at if (ImGui::Selectable(items[n], is_selected)

@ocornut ocornut added the doc label May 28, 2021
@ocornut ocornut changed the title Tips: using BeginCombo() Using BeginCombo() and avanced: custom preview, filtering Jun 15, 2021
@ocornut
Copy link
Owner Author

ocornut commented Jun 15, 2021

On the topic of customizing the combo preview

I have pushed an experimental API (declared in imgui_internal.h)

if (ImGui::BeginCombo("combo custom", "", flags | ImGuiComboFlags_CustomPreview))
{
    // ...
    ImGui::EndCombo();
}
if (ImGui::BeginComboPreview())
{
    ImGui::ColorButton("##color", ImVec4(1.0f, 0.5f, 0.5f, 1.0f), ImGuiColorEditFlags_NoTooltip | ImGuiColorEditFlags_NoDragDrop, color_square_size);
    ImGui::TextUnformatted(items[item_current_idx]);
    ImGui::EndComboPreview();
}

image

The idea is that BeginComboPreview() will set cursor and clip rect, and EndComboPreview() restores things.
Whereas most custom solutions above would leave the preview unclipped (so glitches would appear when resizing down). The clipping and drawcmd merging currently relies on ImGui:: side max cursor pos, but we will switch to use upcoming ImDrawCmd AABB when available.

If it is works well this may eventually be promoted to a public api (imgui.h)

@ocornut
Copy link
Owner Author

ocornut commented Jun 15, 2021

On full custom combo logic

With 060b6ee I did a small refactor of BeginCombo() to extract BeginComboPopup() out of it.
The idea being that if you have to copy the content of BeginCombo() you are more likely to be able to reuse the BeginComboPopup() parts unchanged, and so your copy of BeginCombo() can be smaller (removed ~45 lines).

That said, I think it should now be possible to implement variety of filter idioms without copying/touching BeginCombo() (possibly by using SetItemAllowOverlap). I encourage you all to try and let me know.

@the-goodies
Copy link

So, is it already possible to make a simple ComboFilter/Autocomplete widget using this additional functionality? Such useful widget, yet all provided "examples" in this thread and others are non-working/non-compiling.

@ocornut
Copy link
Owner Author

ocornut commented Jun 16, 2021

I don't know I haven't tried to make one. Perhaps something worth investigating for a demo.

@slajerek
Copy link

slajerek commented Jun 16, 2021

Cool. Will check this. By the way, I've spent a while to fix code from @kovewnikov Not sure if I did this best way, but works quite OK for me. Here's the code: imguiComboFilter.zip

ezgif com-video-to-gif-4

@ChenRenault
Copy link

ChenRenault commented Jul 25, 2021

I just stumbled upon how FlatUI handles the combo filtering, and its logic fits better with IMGUI mentality IMO.

I will try to put the filter inside the combo popup (and leave the header to behave exactly like current Combo). Will create a new snippet someday.

image

flat-ui demo: http://designmodo.github.io/Flat-UI/

ComboWithFilter

Source Code
namespace ImGui
{

    // https://github.com/forrestthewoods/lib_fts

    // Forward declarations for "private" implementation
    namespace fuzzy_internal {
        static bool fuzzy_match_recursive(const char* pattern, const char* str, int& outScore, const char* strBegin,
            uint8_t const* srcMatches, uint8_t* newMatches, int maxMatches, int nextMatch,
            int& recursionCount, int recursionLimit);
    }
    // Private implementation
    static bool fuzzy_internal::fuzzy_match_recursive(const char* pattern, const char* str, int& outScore,
        const char* strBegin, uint8_t const* srcMatches, uint8_t* matches, int maxMatches,
        int nextMatch, int& recursionCount, int recursionLimit)
    {
        // Count recursions
        ++recursionCount;
        if (recursionCount >= recursionLimit)
            return false;

        // Detect end of strings
        if (*pattern == '\0' || *str == '\0')
            return false;

        // Recursion params
        bool recursiveMatch = false;
        uint8_t bestRecursiveMatches[256];
        int bestRecursiveScore = 0;

        // Loop through pattern and str looking for a match
        bool first_match = true;
        while (*pattern != '\0' && *str != '\0') {

            // Found match
            if (tolower(*pattern) == tolower(*str)) {

                // Supplied matches buffer was too short
                if (nextMatch >= maxMatches)
                    return false;

                // "Copy-on-Write" srcMatches into matches
                if (first_match && srcMatches) {
                    memcpy(matches, srcMatches, nextMatch);
                    first_match = false;
                }

                // Recursive call that "skips" this match
                uint8_t recursiveMatches[256];
                int recursiveScore;
                if (fuzzy_match_recursive(pattern, str + 1, recursiveScore, strBegin, matches, recursiveMatches, sizeof(recursiveMatches), nextMatch, recursionCount, recursionLimit)) {

                    // Pick best recursive score
                    if (!recursiveMatch || recursiveScore > bestRecursiveScore) {
                        memcpy(bestRecursiveMatches, recursiveMatches, 256);
                        bestRecursiveScore = recursiveScore;
                    }
                    recursiveMatch = true;
                }

                // Advance
                matches[nextMatch++] = (uint8_t)(str - strBegin);
                ++pattern;
            }
            ++str;
        }

        // Determine if full pattern was matched
        bool matched = *pattern == '\0' ? true : false;

        // Calculate score
        if (matched) {
            const int sequential_bonus = 15;            // bonus for adjacent matches
            const int separator_bonus = 30;             // bonus if match occurs after a separator
            const int camel_bonus = 30;                 // bonus if match is uppercase and prev is lower
            const int first_letter_bonus = 15;          // bonus if the first letter is matched

            const int leading_letter_penalty = -5;      // penalty applied for every letter in str before the first match
            const int max_leading_letter_penalty = -15; // maximum penalty for leading letters
            const int unmatched_letter_penalty = -1;    // penalty for every letter that doesn't matter

            // Iterate str to end
            while (*str != '\0')
                ++str;

            // Initialize score
            outScore = 100;

            // Apply leading letter penalty
            int penalty = leading_letter_penalty * matches[0];
            if (penalty < max_leading_letter_penalty)
                penalty = max_leading_letter_penalty;
            outScore += penalty;

            // Apply unmatched penalty
            int unmatched = (int)(str - strBegin) - nextMatch;
            outScore += unmatched_letter_penalty * unmatched;

            // Apply ordering bonuses
            for (int i = 0; i < nextMatch; ++i) {
                uint8_t currIdx = matches[i];

                if (i > 0) {
                    uint8_t prevIdx = matches[i - 1];

                    // Sequential
                    if (currIdx == (prevIdx + 1))
                        outScore += sequential_bonus;
                }

                // Check for bonuses based on neighbor character value
                if (currIdx > 0) {
                    // Camel case
                    char neighbor = strBegin[currIdx - 1];
                    char curr = strBegin[currIdx];
                    if (::islower(neighbor) && ::isupper(curr))
                        outScore += camel_bonus;

                    // Separator
                    bool neighborSeparator = neighbor == '_' || neighbor == ' ';
                    if (neighborSeparator)
                        outScore += separator_bonus;
                }
                else {
                    // First letter
                    outScore += first_letter_bonus;
                }
            }
        }

        // Return best result
        if (recursiveMatch && (!matched || bestRecursiveScore > outScore)) {
            // Recursive score is better than "this"
            memcpy(matches, bestRecursiveMatches, maxMatches);
            outScore = bestRecursiveScore;
            return true;
        }
        else if (matched) {
            // "this" score is better than recursive
            return true;
        }
        else {
            // no match
            return false;
        }
    }



    static bool fuzzy_match(char const* pattern, char const* str, int& outScore, uint8_t* matches, int maxMatches) {
        int recursionCount = 0;
        int recursionLimit = 10;

        return fuzzy_internal::fuzzy_match_recursive(pattern, str, outScore, str, nullptr, matches, maxMatches, 0, recursionCount, recursionLimit);
    }

    // Public interface
    bool fuzzy_match_simple(char const* pattern, char const* str) {
        while (*pattern != '\0' && *str != '\0') {
            if (tolower(*pattern) == tolower(*str))
                ++pattern;
            ++str;
        }

        return *pattern == '\0' ? true : false;
    }

    bool fuzzy_match(char const* pattern, char const* str, int& outScore) {

        uint8_t matches[256];
        return fuzzy_match(pattern, str, outScore, matches, sizeof(matches));
    }

    static bool sortbysec_desc(const std::pair<int, int>& a, const std::pair<int, int>& b)
    {
        return (b.second < a.second);
    }

    bool ComboWithFilter(const char* label, int* current_item, const std::vector<std::string>& items)
    {
        ImGuiContext& g = *GImGui;

        ImGuiWindow* window = GetCurrentWindow();
        if (window->SkipItems)
            return false;

        const ImGuiStyle& style = g.Style;
        int items_count = items.size();

        // Call the getter to obtain the preview string which is a parameter to BeginCombo()
        const char* preview_value = NULL;
        if (*current_item >= 0 && *current_item < items_count)
            preview_value = items[*current_item].c_str();

        static char pattern_buffer[256] = { 0 };
        bool isNeedFilter = false;

        char comboButtonName[512] = { 0 };
        ImFormatString(comboButtonName, IM_ARRAYSIZE(comboButtonName), "%s##name_ComboWithFilter_button_%s", preview_value? preview_value:"", label);

        char name_popup[256 + 10];
        ImFormatString(name_popup, IM_ARRAYSIZE(name_popup), "##name_popup_%s", label);

        // Display items
        // FIXME-OPT: Use clipper (but we need to disable it on the appearing frame to make sure our call to SetItemDefaultFocus() is processed)
        bool value_changed = false;

        const float expected_w = CalcItemWidth();
        ImVec2 item_min = GetItemRectMin();
        bool isNewOpen = false;
        float sz = GetFrameHeight();
        ImVec2 size(sz, sz);
        ImVec2 CursorPos = window->DC.CursorPos;
        ImVec2 pos = CursorPos + ImVec2(expected_w-sz, 0);
        const ImRect bb(pos, pos + size);

        float ButtonTextAlignX = g.Style.ButtonTextAlign.x;
        g.Style.ButtonTextAlign.x = 0;
        if (ImGui::Button(comboButtonName, ImVec2(expected_w, 0)))
        {
            ImGui::OpenPopup(name_popup);
            isNewOpen = true;
        }
        g.Style.ButtonTextAlign.x = ButtonTextAlignX;
        bool hovered = IsItemHovered();
        bool active = IsItemActivated();
        bool pressed = IsItemClicked();

        // Render
        //const ImU32 bg_col = GetColorU32((active && hovered) ? ImGuiCol_ButtonActive : hovered ? ImGuiCol_ButtonHovered : ImGuiCol_Button);
        //RenderFrame(bb.Min, bb.Max, bg_col, true, g.Style.FrameRounding);
        const ImU32 text_col = GetColorU32(ImGuiCol_Text);
        RenderArrow(window->DrawList, bb.Min + ImVec2(ImMax(0.0f, (size.x - g.FontSize) * 0.5f), ImMax(0.0f, (size.y - g.FontSize) * 0.5f)), text_col, ImGuiDir_Down);

        if (isNewOpen)
        {
            memset(pattern_buffer, 0, IM_ARRAYSIZE(pattern_buffer));
        }
        ImVec2 item_max = GetItemRectMax();
        SetNextWindowPos({ CursorPos.x, item_max.y });
        ImGui::SetNextWindowSize({ ImGui::GetItemRectSize().x, 0 });
        if (ImGui::BeginPopup(name_popup))
        {
            ImGui::PushStyleColor(ImGuiCol_FrameBg, (ImVec4)ImColor(240, 240, 240, 255));
            ImGui::PushStyleColor(ImGuiCol_Text, (ImVec4)ImColor(0, 0, 0, 255));
            ImGui::PushItemWidth(-FLT_MIN);
            // Filter input
            if (isNewOpen)
                ImGui::SetKeyboardFocusHere();
            InputText("##ComboWithFilter_inputText", pattern_buffer, 256);

            // Search Icon, you can use it if you load IconsFontAwesome5 https://github.com/juliettef/IconFontCppHeaders
            //const ImVec2 label_size = CalcTextSize(ICON_FA_SEARCH, NULL, true);
            //const ImVec2 search_icon_pos(ImGui::GetItemRectMax().x - label_size.x - style.ItemInnerSpacing.x * 2, window->DC.CursorPos.y + style.FramePadding.y + g.FontSize * 0.1f);
            //RenderText(search_icon_pos, ICON_FA_SEARCH);

            ImGui::PopStyleColor(2);
            if (pattern_buffer[0] != '\0')
            {
                isNeedFilter = true;
            }

            std::vector<std::pair<int, int> > itemScoreVector;
            if (isNeedFilter)
            {
                for (int i = 0; i < items_count; i++)
                {
                    int score = 0;
                    bool matched = fuzzy_match(pattern_buffer, items[i].c_str(), score);
                    if (matched)
                        itemScoreVector.push_back(std::make_pair(i, score));
                }
                std::sort(itemScoreVector.begin(), itemScoreVector.end(), sortbysec_desc);
            }

            int show_count = isNeedFilter ? itemScoreVector.size() : items_count;
            if (ImGui::ListBoxHeader("##ComboWithFilter_itemList", show_count))
            {
                for (int i = 0; i < show_count; i++)
                {
                    int idx = isNeedFilter ? itemScoreVector[i].first : i;
                    PushID((void*)(intptr_t)idx);
                    const bool item_selected = (idx == *current_item);
                    const char* item_text = items[idx].c_str();
                    if (Selectable(item_text, item_selected))
                    {
                        value_changed = true;
                        *current_item = idx;
                        CloseCurrentPopup();
                    }
                    if (item_selected)
                        SetItemDefaultFocus();
                    PopID();
                }
                ImGui::ListBoxFooter();
            }
            ImGui::PopItemWidth();
            ImGui::EndPopup();
        }


        if (value_changed)
            MarkItemEdited(g.CurrentWindow->DC.LastItemId);

        return value_changed;
    }
}

@idbrii
Copy link
Contributor

idbrii commented Apr 1, 2022

Edit: updated my version of ComboWithFilter for v1.89 WIP. Looks the same as old gif below.


Testing on imgui 1.78 WIP, I tried some of the above combo filters.

After fixing some deprecated functions, I still couldn't get r-lyeh's ComboFilter to accept any text (immediately loses focus). kovewnikov's and slajerek's versions work better, but not if there are multiple ComboFilters visible at once (then it won't accept more than one character). Possibly it's my fault since I used a static buffer and ComboFilterState.

ChenRenault's ComboWithFilter worked wonderfully. Putting the filter inside the combo makes the api simpler and I can have multiple visible at once.

I extended ComboWithFilter to add arrow navigation, Enter to confirm, and max_height_in_items. It uses BeginCombo to avoids drawing beyond the edge of the window and I fixed focus on open:
https://gist.github.com/idbrii/5ddb2135ca122a0ec240ce046d9e6030

combo-filter

@kwonjinyoung
Copy link

kwonjinyoung commented Apr 22, 2022

Dear idbrii

hi
I tried your source code on version 1.87.
But it's not working properly.
Can you test it on version 1.87?
thank you.

@ambrosiogabe
Copy link

Hi @kwonjinyoung I left a comment on the gist because it did not work for me either in 1.87. I believe the changes that I've posted in the comment should be all that's necessary to get this to work in 1.87.

@SirDragonClaw
Copy link

@ocornut

On the topic of customizing the combo preview

I have pushed an experimental API (declared in imgui_internal.h)

If it is works well this may eventually be promoted to a public api (imgui.h)

Hey I cannot find this experimental branch, and I can't find this in master. Did this get removed?

@ocornut
Copy link
Owner Author

ocornut commented Jun 8, 2022

Its all still here in imgui_internal.h

@ozlb
Copy link

ozlb commented Aug 23, 2022

If somebody is interested I changed #1658 (comment) into imgui_combo_autoselect.h and did a minor code cleanup, changed function signature as per old API Combo() with item_getter callback (in this way can be used in much more dynamic data context)

https://gist.github.com/ozlb/9cd35891aa4de3450e8e4c844837e7f9

const char* hints[] = {
				"AnimGraphNode_CopyBone",
				"ce skipaa",
				"ce skipscreen",
				"ce skipsplash",
				"ce skipsplashscreen",
				"client_unit.cpp",
				"letrograd",
				"level",
				"leveler",
				"MacroCallback.cpp",
				"Miskatonic university",
				"MockAI.h",
				"MockGameplayTasks.h",
				"MovieSceneColorTrack.cpp",
				"r.maxfps",
				"r.maxsteadyfps",
				"reboot",
				"rescale",
				"reset",
				"resource",
				"restart",
				"retrocomputer",
				"retrograd",
				"return",
				"slomo 10",
				"SVisualLoggerLogsList.h",
				"The Black Knight",
};
static int comboSelection = 0;
static char buf[128] = { 0x00 };
static char sel[128] = { 0x00 };
struct Funcs { static bool ItemGetter(void* data, int n, const char** out_str) { *out_str = ((const char**)data)[n]; return true; } };
if (ImGui::ComboAutoSelect("my combofilter", buf, IM_ARRAYSIZE(buf), &comboSelection, &Funcs::ItemGetter, hints, IM_ARRAYSIZE(hints), NULL)) {
	//...picking has occurred
	sprintf(sel, "%s", buf);
}
ImGui::Text("Selection: %s", sel);

@sweihub
Copy link

sweihub commented Sep 23, 2022

Hi @idbrii

Thanks fo your code, howerver, it dose not support the CKJ characters, and the search icon is gone, can you fix?
I set the default font to display Chinese.

io.Fonts->AddFontFromFileTTF("c:\\Windows\\Fonts\\msyh.ttc", 16.0f, NULL, io.Fonts->GetGlyphRangesChineseFull());

image

@sweihub
Copy link

sweihub commented Sep 23, 2022

@idbrii
I fixed the Chinese input issue with the solution from #1807 (comment)

And fixed an assertion crash, but the search icon is still not displayed.

diff --git a/imgui/fts_fuzzy_match.h b/imgui/fts_fuzzy_match.h
index 523982e..2267dcb 100644
--- a/imgui/fts_fuzzy_match.h
+++ b/imgui/fts_fuzzy_match.h
@@ -184,7 +184,8 @@ namespace fts {
                     char neighbor = strBegin[currIdx - 1];
                     char curr = strBegin[currIdx];

-                    if (::islower(neighbor) && ::isupper(curr))
+                    // fix for utf-8
+                    if (neighbor > 0 && curr > 0 && ::islower(neighbor) && ::isupper(curr))
                         outScore += camel_bonus;

                     // Separator

image

I also tried with @ozlb ImGui::ComboAutoSelect, it just works, but RETURN key dose not select the first match! Anyway, thanks!

image

@ChenRenault
Copy link

My attempt to imitate VSCode, source code by https://github.com/hnOsmium0001/imgui-command-palette
dear imgui, v1.84
small

Source Code

source code

imgui_extentions.h

#pragma once

#include <string>
#include <vector>
#include "imgui/imgui.h"
// #include "CCImguiMacros.h"
// namespace ccimgui {}
#ifdef __cplusplus
    #define NS_CCIMGUI_BEGIN                     namespace ccimgui {
    #define NS_CCIMGUI_END                       }
    #define USING_NS_CCIMGUI                     using namespace ccimgui
    #define NS_CCIMGUI                           ::ccimgui
#else
    #define NS_CCIMGUI_BEGIN 
    #define NS_CCIMGUI_END 
    #define USING_NS_CCIMGUI 
    #define NS_CCIMGUI
#endif 


NS_CCIMGUI_BEGIN

IMGUI_API bool FuzzySearch(char const* pattern, char const* src, int& outScore);
IMGUI_API bool FuzzySearch(char const* pattern, char const* src, int& outScore, uint8_t matches[], int maxMatches, int& outMatches);

IMGUI_API void InitExtentionsContext();

IMGUI_API bool Combo(const char* label, int* current_item, const std::vector<std::string>& items, int popup_max_height_in_items = -1);
IMGUI_API bool ComboWithFilter(const char* label, int* current_item, const std::vector<std::string>& items, int popup_max_height_in_items = -1);

IMGUI_API bool ListBox(const char* label, int* current_item, const std::vector<std::string>& items, int height_in_items = -1);
IMGUI_API bool ListBoxWithFilter(const char* label, int* current_item, const std::vector<std::string>& items, int height_in_items = -1);

NS_CCIMGUI_END

imgui_extentions.cpp

#include <cctype>
#include <algorithm>
#include <cstring>
#include <limits>
#include <utility>

#include "imgui_extentions.h"

#include "imgui/imgui.h"
#ifndef IMGUI_DEFINE_MATH_OPERATORS
#define IMGUI_DEFINE_MATH_OPERATORS
#endif
#include "imgui/imgui_internal.h"

#ifdef IMGUI_ICONSFONT_ENABLED
// #include "IconsFontAwesome5.h"
#include "IconsMaterialDesign.h"
#endif


static size_t HashCString(const char* p)
{
    size_t result = 0;
    constexpr size_t kPrime = 31;
    for (size_t i = 0; p[i] != '\0'; ++i) {
        result = p[i] + (result * kPrime);
    }
    return result;
}

NS_CCIMGUI_BEGIN

namespace
{
    bool FuzzySearchRecursive(const char* pattern, const char* src, int& outScore, const char* strBegin, const uint8_t srcMatches[], uint8_t newMatches[], int maxMatches, int& nextMatch, int& recursionCount, int recursionLimit);
} // namespace

bool FuzzySearch(char const* pattern, char const* haystack, int& outScore)
{
    uint8_t matches[256];
    int matchCount = 0;
    return FuzzySearch(pattern, haystack, outScore, matches, sizeof(matches), matchCount);
}

bool FuzzySearch(char const* pattern, char const* haystack, int& outScore, uint8_t matches[], int maxMatches, int& outMatches)
{
    int recursionCount = 0;
    int recursionLimit = 10;
    int newMatches = 0;
    bool result = FuzzySearchRecursive(pattern, haystack, outScore, haystack, nullptr, matches, maxMatches, newMatches, recursionCount, recursionLimit);
    outMatches = newMatches;
    return result;
}

namespace
{
    bool FuzzySearchRecursive(const char* pattern, const char* src, int& outScore, const char* strBegin, const uint8_t srcMatches[], uint8_t newMatches[], int maxMatches, int& nextMatch, int& recursionCount, int recursionLimit)
    {
        // Count recursions
        ++recursionCount;
        if (recursionCount >= recursionLimit) {
            return false;
        }

        // Detect end of strings
        if (*pattern == '\0' || *src == '\0') {
            return false;
        }

        // Recursion params
        bool recursiveMatch = false;
        uint8_t bestRecursiveMatches[256];
        int bestRecursiveScore = 0;

        // Loop through pattern and str looking for a match
        bool firstMatch = true;
        while (*pattern != '\0' && *src != '\0') {
            // Found match
            if (tolower(*pattern) == tolower(*src)) {
                // Supplied matches buffer was too short
                if (nextMatch >= maxMatches) {
                    return false;
                }

                // "Copy-on-Write" srcMatches into matches
                if (firstMatch && srcMatches) {
                    memcpy(newMatches, srcMatches, nextMatch);
                    firstMatch = false;
                }

                // Recursive call that "skips" this match
                uint8_t recursiveMatches[256];
                int recursiveScore;
                int recursiveNextMatch = nextMatch;
                if (FuzzySearchRecursive(pattern, src + 1, recursiveScore, strBegin, newMatches, recursiveMatches, sizeof(recursiveMatches), recursiveNextMatch, recursionCount, recursionLimit)) {
                    // Pick the best recursive score
                    if (!recursiveMatch || recursiveScore > bestRecursiveScore) {
                        memcpy(bestRecursiveMatches, recursiveMatches, 256);
                        bestRecursiveScore = recursiveScore;
                    }
                    recursiveMatch = true;
                }

                // Advance
                newMatches[nextMatch++] = (uint8_t)(src - strBegin);
                ++pattern;
            }
            ++src;
        }

        // Determine if full pattern was matched
        bool matched = *pattern == '\0';

        // Calculate score
        if (matched) {
            const int sequentialBonus = 15; // bonus for adjacent matches
            const int separatorBonus = 30; // bonus if match occurs after a separator
            const int camelBonus = 30; // bonus if match is uppercase and prev is lower
            const int firstLetterBonus = 15; // bonus if the first letter is matched

            const int leadingLetterPenalty = -5; // penalty applied for every letter in str before the first match
            const int maxLeadingLetterPenalty = -15; // maximum penalty for leading letters
            const int unmatchedLetterPenalty = -1; // penalty for every letter that doesn't matter

            // Iterate str to end
            while (*src != '\0') {
                ++src;
            }

            // Initialize score
            outScore = 100;

            // Apply leading letter penalty
            int penalty = leadingLetterPenalty * newMatches[0];
            if (penalty < maxLeadingLetterPenalty) {
                penalty = maxLeadingLetterPenalty;
            }
            outScore += penalty;

            // Apply unmatched penalty
            int unmatched = (int)(src - strBegin) - nextMatch;
            outScore += unmatchedLetterPenalty * unmatched;

            // Apply ordering bonuses
            for (int i = 0; i < nextMatch; ++i) {
                uint8_t currIdx = newMatches[i];

                if (i > 0) {
                    uint8_t prevIdx = newMatches[i - 1];

                    // Sequential
                    if (currIdx == (prevIdx + 1))
                        outScore += sequentialBonus;
                }

                // Check for bonuses based on neighbor character value
                if (currIdx > 0) {
                    // Camel case
                    char neighbor = strBegin[currIdx - 1];
                    char curr = strBegin[currIdx];
                    if (::islower(neighbor) && ::isupper(curr)) {
                        outScore += camelBonus;
                    }

                    // Separator
                    bool neighborSeparator = neighbor == '_' || neighbor == ' ';
                    if (neighborSeparator) {
                        outScore += separatorBonus;
                    }
                } else {
                    // First letter
                    outScore += firstLetterBonus;
                }
            }
        }

        // Return best result
        if (recursiveMatch && (!matched || bestRecursiveScore > outScore)) {
            // Recursive score is better than "this"
            memcpy(newMatches, bestRecursiveMatches, maxMatches);
            outScore = bestRecursiveScore;
            return true;
        } else if (matched) {
            // "this" score is better than recursive
            return true;
        } else {
            // no match
            return false;
        }
    }
} // namespace

struct SearchResult
{
    int ItemIndex;
    int Score;
    int MatchCount;
    uint8_t Matches[32];
};

struct ItemExtraData
{
    bool Hovered = false;
    bool Held = false;
};

struct Instance
{
    std::vector<ItemExtraData> ExtraData;

    int CurrentSelectedItem = 0;
    char pattern_buffer[256];

    struct
    {
        bool RefreshSearch = false;
        bool ClearSearch = false;
    } PendingActions;
};

struct Context
{
    ImGuiStorage Instances;
    Instance* CurrentCommandPalette = nullptr;
};

static Context* gContext = nullptr;

// =================================================================
// API implementation
// =================================================================

Context* CreateExtentionsContext()
{
    auto ctx = new Context();
    if (!gContext) {
        gContext = ctx;
    }
    return ctx;
}

void DestroyExtentionsContext(Context* context)
{
    delete context;
}

void DestroyExtentionsContext()
{
    DestroyExtentionsContext(gContext);
    gContext = nullptr;
}

void SetCurrentExtentionsContext(Context* context)
{
    gContext = context;
}

Context* GetCurrentExtentionsContext()
{
    return gContext;
}

void InitExtentionsContext()
{
    CreateExtentionsContext();
}

static bool sortbysec_desc(const std::pair<int, int>& a, const std::pair<int, int>& b)
{
    return (b.second < a.second);
}
static float CalcMaxPopupHeightFromItemCount(int items_count)
{
    ImGuiContext& g = *GImGui;
    if (items_count <= 0)
        return FLT_MAX;
    return (g.FontSize + g.Style.ItemSpacing.y) * items_count - g.Style.ItemSpacing.y + (g.Style.WindowPadding.y * 2);
}
    
IMGUI_API bool ComboWithFilter(const char* label, int* current_item, const std::vector<std::string>& items, int popup_max_height_in_items)
{
    ImGuiContext& g = *GImGui;
    ImGuiWindow* window = ImGui::GetCurrentWindow();

    int items_count = items.size();
    // Call the getter to obtain the preview string which is a parameter to BeginCombo()
    const char* preview_value = NULL;
    if (*current_item >= 0 && *current_item < items_count)
        preview_value = items[*current_item].c_str();
    
    // The old Combo() API exposed "popup_max_height_in_items". The new more general BeginCombo() API doesn't have/need it, but we emulate it here.
    if (popup_max_height_in_items != -1 && !(g.NextWindowData.Flags & ImGuiNextWindowDataFlags_HasSizeConstraint))
        ImGui::SetNextWindowSizeConstraints(ImVec2(0, 0), ImVec2(FLT_MAX, CalcMaxPopupHeightFromItemCount(popup_max_height_in_items)));

    ImGuiComboFlags flags = ImGuiComboFlags_None;

    ImGuiNextWindowDataFlags backup_next_window_data_flags = g.NextWindowData.Flags;
    g.NextWindowData.ClearFlags(); // We behave like Begin() and need to consume those values
    if (window->SkipItems)
        return false;

    const ImGuiStyle& style = g.Style;
    const ImGuiID id = window->GetID(label);
    IM_ASSERT((flags & (ImGuiComboFlags_NoArrowButton | ImGuiComboFlags_NoPreview)) != (ImGuiComboFlags_NoArrowButton | ImGuiComboFlags_NoPreview)); // Can't use both flags together

    const float arrow_size = (flags & ImGuiComboFlags_NoArrowButton) ? 0.0f : ImGui::GetFrameHeight();
    const ImVec2 label_size = ImGui::CalcTextSize(label, NULL, true);
    const float w = (flags & ImGuiComboFlags_NoPreview) ? arrow_size : ImGui::CalcItemWidth();
    const ImRect bb(window->DC.CursorPos, window->DC.CursorPos + ImVec2(w, label_size.y + style.FramePadding.y * 2.0f));
    const ImRect total_bb(bb.Min, bb.Max + ImVec2(label_size.x > 0.0f ? style.ItemInnerSpacing.x + label_size.x : 0.0f, 0.0f));
    ImGui::ItemSize(total_bb, style.FramePadding.y);
    if (!ImGui::ItemAdd(total_bb, id, &bb))
        return false;

    // Open on click
    bool hovered, held;
    bool pressed = ImGui::ButtonBehavior(bb, id, &hovered, &held);
    const ImGuiID popup_id = ImHashStr("##ComboPopup", 0, id);
    bool popup_open = ImGui::IsPopupOpen(popup_id, ImGuiPopupFlags_None);
    if ((pressed || g.NavActivateId == id) && !popup_open)
    {
        ImGui::OpenPopupEx(popup_id, ImGuiPopupFlags_None);
        popup_open = true;
    }

    // Render shape
    const ImU32 frame_col = ImGui::GetColorU32(hovered ? ImGuiCol_FrameBgHovered : ImGuiCol_FrameBg);
    const float value_x2 = ImMax(bb.Min.x, bb.Max.x - arrow_size);
    ImGui::RenderNavHighlight(bb, id);
    if (!(flags & ImGuiComboFlags_NoPreview))
        window->DrawList->AddRectFilled(bb.Min, ImVec2(value_x2, bb.Max.y), frame_col, style.FrameRounding, (flags & ImGuiComboFlags_NoArrowButton) ? ImDrawFlags_RoundCornersAll : ImDrawFlags_RoundCornersLeft);
    if (!(flags & ImGuiComboFlags_NoArrowButton))
    {
        ImU32 bg_col = ImGui::GetColorU32((popup_open || hovered) ? ImGuiCol_ButtonHovered : ImGuiCol_Button);
        ImU32 text_col = ImGui::GetColorU32(ImGuiCol_Text);
        window->DrawList->AddRectFilled(ImVec2(value_x2, bb.Min.y), bb.Max, bg_col, style.FrameRounding, (w <= arrow_size) ? ImDrawFlags_RoundCornersAll : ImDrawFlags_RoundCornersRight);
        if (value_x2 + arrow_size - style.FramePadding.x <= bb.Max.x)
            ImGui::RenderArrow(window->DrawList, ImVec2(value_x2 + style.FramePadding.y, bb.Min.y + style.FramePadding.y), text_col, ImGuiDir_Down, 1.0f);
    }
    ImGui::RenderFrameBorder(bb.Min, bb.Max, style.FrameRounding);

    // Custom preview
    if (flags & ImGuiComboFlags_CustomPreview)
    {
        g.ComboPreviewData.PreviewRect = ImRect(bb.Min.x, bb.Min.y, value_x2, bb.Max.y);
        IM_ASSERT(preview_value == NULL || preview_value[0] == 0);
        preview_value = NULL;
    }

    // Render preview and label
    if (preview_value != NULL && !(flags & ImGuiComboFlags_NoPreview))
    {
        if (g.LogEnabled)
            ImGui::LogSetNextTextDecoration("{", "}");
        ImGui::RenderTextClipped(bb.Min + style.FramePadding, ImVec2(value_x2, bb.Max.y), preview_value, NULL, NULL);
    }
    if (label_size.x > 0)
        ImGui::RenderText(ImVec2(bb.Max.x + style.ItemInnerSpacing.x, bb.Min.y + style.FramePadding.y), label);

    if (!popup_open)
        return false;

    g.NextWindowData.Flags = backup_next_window_data_flags;

    if (!ImGui::IsPopupOpen(popup_id, ImGuiPopupFlags_None))
    {
        g.NextWindowData.ClearFlags();
        return false;
    }

    // Set popup size
    float bb_w = bb.GetWidth();
    if (g.NextWindowData.Flags & ImGuiNextWindowDataFlags_HasSizeConstraint)
    {
        g.NextWindowData.SizeConstraintRect.Min.x = ImMax(g.NextWindowData.SizeConstraintRect.Min.x, bb_w);
    }
    else
    {
        if ((flags & ImGuiComboFlags_HeightMask_) == 0)
            flags |= ImGuiComboFlags_HeightRegular;
        IM_ASSERT(ImIsPowerOfTwo(flags & ImGuiComboFlags_HeightMask_)); // Only one
        int popup_max_height_in_items = -1;
        if (flags & ImGuiComboFlags_HeightRegular)     popup_max_height_in_items = 8;
        else if (flags & ImGuiComboFlags_HeightSmall)  popup_max_height_in_items = 4;
        else if (flags & ImGuiComboFlags_HeightLarge)  popup_max_height_in_items = 20;
        ImGui::SetNextWindowSizeConstraints(ImVec2(bb_w, 0.0f), ImVec2(FLT_MAX, CalcMaxPopupHeightFromItemCount(popup_max_height_in_items)));
    }

    // This is essentially a specialized version of BeginPopupEx()
    char name[16];
    ImFormatString(name, IM_ARRAYSIZE(name), "##Combo_%02d", g.BeginPopupStack.Size); // Recycle windows based on depth

    // Set position given a custom constraint (peak into expected window size so we can position it)
    // FIXME: This might be easier to express with an hypothetical SetNextWindowPosConstraints() function?
    // FIXME: This might be moved to Begin() or at least around the same spot where Tooltips and other Popups are calling FindBestWindowPosForPopupEx()?
    if (ImGuiWindow* popup_window = ImGui::FindWindowByName(name))
        if (popup_window->WasActive)
        {
            // Always override 'AutoPosLastDirection' to not leave a chance for a past value to affect us.
            ImVec2 size_expected = ImGui::CalcWindowNextAutoFitSize(popup_window);
            popup_window->AutoPosLastDirection = (flags & ImGuiComboFlags_PopupAlignLeft) ? ImGuiDir_Left : ImGuiDir_Down; // Left = "Below, Toward Left", Down = "Below, Toward Right (default)"
            ImRect r_outer = ImGui::GetPopupAllowedExtentRect(popup_window);
            ImVec2 pos = ImGui::FindBestWindowPosForPopupEx(bb.GetBL(), size_expected, &popup_window->AutoPosLastDirection, r_outer, bb, ImGuiPopupPositionPolicy_ComboBox);
            ImGui::SetNextWindowPos(pos);
        }

    // We don't use BeginPopupEx() solely because we have a custom name string, which we could make an argument to BeginPopupEx()
    ImGuiWindowFlags window_flags = ImGuiWindowFlags_Popup | ImGuiWindowFlags_NoTitleBar | ImGuiWindowFlags_NoResize | ImGuiWindowFlags_NoSavedSettings | ImGuiWindowFlags_NoMove | ImGuiWindowFlags_NoScrollbar;
    ImGui::PushStyleVar(ImGuiStyleVar_WindowPadding, ImVec2(g.Style.FramePadding.x, g.Style.WindowPadding.y)); // Horizontally align ourselves with the framed text
    bool ret = ImGui::Begin(name, NULL, window_flags);
    ImGui::PopStyleVar();
    if (!ret)
    {
        ImGui::EndPopup();
        IM_ASSERT(0);   // This should never happen as we tested for IsPopupOpen() above
        return false;
    }
    
    bool value_changed = false;

    auto& gg = *gContext;
    auto& gi = *[&]() {
        auto id = HashCString(label);
        if (auto ptr = gg.Instances.GetVoidPtr(id)) {
            return reinterpret_cast<Instance*>(ptr);
        } else {
            auto instance = new Instance();
            gg.Instances.SetVoidPtr(id, instance);
            return instance;
        }
    }();
    
    static char pattern_buffer[256] = { 0 };
    if (pressed)
        memset(pattern_buffer, 0, IM_ARRAYSIZE(pattern_buffer));
    
    bool isNeedFilter = false;
    // Display items
    {
        ImGui::PushStyleColor(ImGuiCol_FrameBg, (ImVec4)ImColor(240, 240, 240, 255));
        ImGui::PushStyleColor(ImGuiCol_Text, (ImVec4)ImColor(0, 0, 0, 255));
        ImGui::PushItemWidth(-FLT_MIN);
        // Filter input
        if (pressed)
            ImGui::SetKeyboardFocusHere();
        ImGui::InputText("##ComboWithFilter_inputText", pattern_buffer, 256);

#ifdef IMGUI_ICONSFONT_ENABLED
        // Search Icon, you can use it if you load IconsFontAwesome5 https://github.com/juliettef/IconFontCppHeaders
        const ImVec2 label_size = ImGui::CalcTextSize(ICON_MD_SEARCH, NULL, true);
        const ImVec2 search_icon_pos(ImGui::GetItemRectMax().x - label_size.x - style.ItemInnerSpacing.x * 2, window->DC.CursorPos.y + style.FramePadding.y + g.FontSize * 0.1f);
        ImGui::RenderText(search_icon_pos, ICON_MD_SEARCH);
#endif

        ImGui::PopStyleColor(2);
        if (pattern_buffer[0] != '\0')
            isNeedFilter = true;

        std::vector<SearchResult> SearchResults;
        if (isNeedFilter)
        {
            for (int i = 0; i < items_count; i++)
            {
                SearchResult result;
                if (FuzzySearch(pattern_buffer, items[i].c_str(), result.Score, result.Matches, IM_ARRAYSIZE(result.Matches), result.MatchCount)) {
                    result.ItemIndex = i;
                    SearchResults.push_back(result);
                }
            }
            std::sort(SearchResults.begin(), SearchResults.end(), [](const SearchResult& a, const SearchResult& b) -> bool {
                // We want the biggest element first
                return a.Score > b.Score;
            });
        }

        int show_count = isNeedFilter ? SearchResults.size() : items_count;
        auto font_regular = ImGui::GetDrawListSharedData()->Font;
        auto font_highlight = ImGui::GetDrawListSharedData()->Font;

        ImU32 text_color_regular = ImGui::GetColorU32(ImGuiCol_Text);
        ImU32 text_color_highlight = ImGui::ColorConvertFloat4ToU32(ImVec4(24.0f/255.0f, 163.0f/255.0f, 1.0f, 1.0f));
        
        ImU32 item_hovered_color = ImGui::GetColorU32(ImGuiCol_HeaderHovered);
        ImU32 item_active_color = ImGui::GetColorU32(ImGuiCol_HeaderActive);
        ImU32 item_selected_color = ImGui::GetColorU32(ImGuiCol_Header);

        if (gi.ExtraData.size() < show_count)
            gi.ExtraData.resize(show_count);

        bool select_focused_item = false;

        // Calculate size from "height_in_items"
        if (popup_max_height_in_items < 0)
            popup_max_height_in_items = ImMin(show_count, 7);
        float height_in_items_f = popup_max_height_in_items + 0.25f;
        ImVec2 size(0.0f, ImFloor(ImGui::GetTextLineHeightWithSpacing() * height_in_items_f + g.Style.FramePadding.y * 2.0f));

        if (ImGui::BeginListBox(label, size))
        {
            ImGuiWindow* window = ImGui::GetCurrentWindow();
            ImDrawList* draw_list = window->DrawList;
            const float font_size = window->CalcFontSize();

            for (int i = 0; i < show_count; ++i) {
                int idx = isNeedFilter ? SearchResults[i].ItemIndex : i;
                const bool item_selected = (idx == *current_item);
                const char* item_text = items[idx].c_str();
                ImGuiID id = window->GetID(static_cast<int>(i));

                ImGuiSelectableFlags flags = 0;
                
                const ImVec2 size_arg(0.0f, 0.0f);
                ImVec2 label_size = ImGui::CalcTextSize(item_text, NULL, true);
                ImVec2 size(size_arg.x != 0.0f ? size_arg.x : label_size.x, size_arg.y != 0.0f ? size_arg.y : label_size.y);
                ImVec2 pos = window->DC.CursorPos;
                pos.y += window->DC.CurrLineTextBaseOffset;

                // Fill horizontal space
                // We don't support (size < 0.0f) in Selectable() because the ItemSpacing extension would make explicitly right-aligned sizes not visibly match other widgets.
                const bool span_all_columns = (flags & ImGuiSelectableFlags_SpanAllColumns) != 0;
                const float min_x = span_all_columns ? window->ParentWorkRect.Min.x : pos.x;
                const float max_x = span_all_columns ? window->ParentWorkRect.Max.x : window->WorkRect.Max.x;
                if (size_arg.x == 0.0f || (flags & ImGuiSelectableFlags_SpanAvailWidth))
                    size.x = ImMax(label_size.x, max_x - min_x);

                // Text stays at the submission position, but bounding box may be extended on both sides
                // const ImVec2 text_min = pos;
                const ImVec2 text_max(min_x + size.x, pos.y + size.y);

                // Selectables are meant to be tightly packed together with no click-gap, so we extend their box to cover spacing between selectable.
                ImRect rect(min_x, pos.y, text_max.x, text_max.y);

                bool& hovered = gi.ExtraData[i].Hovered;
                bool& held = gi.ExtraData[i].Held;
                if (held && hovered) {
                    draw_list->AddRectFilled(rect.Min, rect.Max, item_active_color);
                } else if (hovered) {
                    draw_list->AddRectFilled(rect.Min, rect.Max, item_hovered_color);
                } else if (gi.CurrentSelectedItem == i) {
                    draw_list->AddRectFilled(rect.Min, rect.Max, item_selected_color);
                }

                if (isNeedFilter) {
                    // Iterating search results: draw text with highlights at matched chars

                    auto& search_result = SearchResults[i];

                    auto text_pos = window->DC.CursorPos;
                    int range_begin;
                    int range_end;
                    int last_range_end = 0;

                    auto DrawCurrentRange = [&]() {
                        if (range_begin != last_range_end) {
                            // Draw normal text between last highlighted range end and current highlighted range start
                            auto begin = item_text + last_range_end;
                            auto end = item_text + range_begin;
                            draw_list->AddText(text_pos, text_color_regular, begin, end);

                            auto segment_size = font_regular->CalcTextSizeA(font_size, std::numeric_limits<float>::max(), 0.0f, begin, end);
                            text_pos.x += segment_size.x;
                        }

                        auto begin = item_text + range_begin;
                        auto end = item_text + range_end;
                        draw_list->AddText(text_pos, text_color_highlight, begin, end);

                        auto segment_size = font_highlight->CalcTextSizeA(font_size, std::numeric_limits<float>::max(), 0.0f, begin, end);
                        text_pos.x += segment_size.x;
                    };

                    IM_ASSERT(search_result.MatchCount >= 1);
                    range_begin = search_result.Matches[0];
                    range_end = range_begin;

                    int last_char_idx = -1;
                    for (int j = 0; j < search_result.MatchCount; ++j) {
                        int char_idx = search_result.Matches[j];

                        if (char_idx == last_char_idx + 1) {
                            // These 2 indices are equal, extend our current range by 1
                            ++range_end;
                        } else {
                            DrawCurrentRange();
                            last_range_end = range_end;
                            range_begin = char_idx;
                            range_end = char_idx + 1;
                        }

                        last_char_idx = char_idx;
                    }

                    // Draw the remaining range (if any)
                    if (range_begin != range_end) {
                        DrawCurrentRange();
                    }

                    // Draw the text after the last range (if any)
                    draw_list->AddText(text_pos, text_color_regular, item_text + range_end); // Draw until \0
                } else {
                    // Iterating everything else: draw text as-is, there is no highlights
                    draw_list->AddText(pos, text_color_regular, item_text);
                }

                ImGui::ItemSize(rect);
                if (ImGui::ItemAdd(rect, id)) {                        
                    if (ImGui::ButtonBehavior(rect, id, &hovered, &held)) {
                        gi.CurrentSelectedItem = i;
                        select_focused_item = true;
                        value_changed = true;
                        *current_item = idx;
                        ImGui::CloseCurrentPopup();
                    }
                }
                
                if (item_selected)
                {
                    ImGui::SetItemDefaultFocus();
                    if (g.CurrentWindow->Appearing)
                    {
                        ImGui::SetScrollHereY(0.5f);
                    }
                }
            }


            ImGui::EndListBox();
        }
        ImGui::PopItemWidth();
    }
    ImGui::EndPopup();

    if (value_changed)
        ImGui::MarkItemEdited(g.LastItemData.ID);

    return value_changed;
}

IMGUI_API bool Combo(const char* label, int* current_item, const std::vector<std::string>& items, int popup_max_height_in_items)
{
    int items_count = items.size();
    ImGuiContext& g = *GImGui;

    // Call the getter to obtain the preview string which is a parameter to BeginCombo()
    const char* preview_value = NULL;
    if (*current_item >= 0 && *current_item < items_count)
        preview_value = items[*current_item].c_str();

    // The old Combo() API exposed "popup_max_height_in_items". The new more general BeginCombo() API doesn't have/need it, but we emulate it here.
    if (popup_max_height_in_items != -1 && !(g.NextWindowData.Flags & ImGuiNextWindowDataFlags_HasSizeConstraint))
        ImGui::SetNextWindowSizeConstraints(ImVec2(0, 0), ImVec2(FLT_MAX, CalcMaxPopupHeightFromItemCount(popup_max_height_in_items)));

    if (!ImGui::BeginCombo(label, preview_value, ImGuiComboFlags_None))
        return false;

    // Display items
    // FIXME-OPT: Use clipper (but we need to disable it on the appearing frame to make sure our call to SetItemDefaultFocus() is processed)
    bool value_changed = false;
    for (int i = 0; i < items_count; i++)
    {
        ImGui::PushID((void*)(intptr_t)i);
        const bool item_selected = (i == *current_item);
        const char* item_text = items[i].c_str();
        if (ImGui::Selectable(item_text, item_selected))
        {
            value_changed = true;
            *current_item = i;
        }
        if (item_selected)
            ImGui::SetItemDefaultFocus();
        ImGui::PopID();
    }

    ImGui::EndCombo();

    if (value_changed)
        ImGui::MarkItemEdited(g.LastItemData.ID);

    return value_changed;
}

IMGUI_API bool ListBox(const char* label, int* current_item, const std::vector<std::string>& items, int height_in_items)
{
    int items_count = items.size();
    ImGuiContext& g = *GImGui;

    // Calculate size from "height_in_items"
    if (height_in_items < 0)
        height_in_items = ImMin(items_count, 7);
    float height_in_items_f = height_in_items + 0.25f;
    ImVec2 size(0.0f, ImFloor(ImGui::GetTextLineHeightWithSpacing() * height_in_items_f + g.Style.FramePadding.y * 2.0f));

    if (!ImGui::BeginListBox(label, size))
        return false;

    // Assume all items have even height (= 1 line of text). If you need items of different height,
    // you can create a custom version of ListBox() in your code without using the clipper.
    bool value_changed = false;
    ImGuiListClipper clipper;
    clipper.Begin(items_count, ImGui::GetTextLineHeightWithSpacing()); // We know exactly our line height here so we pass it as a minor optimization, but generally you don't need to.
    while (clipper.Step())
        for (int i = clipper.DisplayStart; i < clipper.DisplayEnd; i++)
        {
            const char* item_text = items[i].c_str();

            ImGui::PushID(i);
            const bool item_selected = (i == *current_item);
            if (ImGui::Selectable(item_text, item_selected))
            {
                *current_item = i;
                value_changed = true;
            }
            if (item_selected)
                ImGui::SetItemDefaultFocus();
            ImGui::PopID();
        }
    ImGui::EndListBox();

    if (value_changed)
        ImGui::MarkItemEdited(g.LastItemData.ID);

    return value_changed;
}

IMGUI_API bool ListBoxWithFilter(const char* label, int* current_item, const std::vector<std::string>& items, int height_in_items)
{
    int items_count = items.size();
    ImGuiContext& g = *GImGui;
    const ImGuiStyle& style = g.Style;

    // Calculate size from "height_in_items"
    if (height_in_items < 0)
        height_in_items = ImMin(items_count, 7);
    float height_in_items_f = height_in_items + 0.25f;
    ImVec2 size(0.0f, ImFloor(ImGui::GetTextLineHeightWithSpacing() * height_in_items_f + g.Style.FramePadding.y * 2.0f));

    bool value_changed = false;

    auto& gg = *gContext;
    auto& gi = *[&]() {
        auto id = HashCString(label);
        if (auto ptr = gg.Instances.GetVoidPtr(id)) {
            return reinterpret_cast<Instance*>(ptr);
        } else {
            auto instance = new Instance();
            gg.Instances.SetVoidPtr(id, instance);
            return instance;
        }
    }();
    ImGuiWindow* window = ImGui::GetCurrentWindow();
        
    bool isNeedFilter = false;
    // Display items
    {
        ImGui::PushStyleColor(ImGuiCol_FrameBg, (ImVec4)ImColor(240, 240, 240, 255));
        ImGui::PushStyleColor(ImGuiCol_Text, (ImVec4)ImColor(0, 0, 0, 255));
        ImGui::PushItemWidth(-FLT_MIN);
        ImGui::InputText("##ComboWithFilter_inputText", gi.pattern_buffer, 256);

#ifdef IMGUI_ICONSFONT_ENABLED
        // Search Icon, you can use it if you load IconsFontAwesome5 https://github.com/juliettef/IconFontCppHeaders
        const ImVec2 label_size = ImGui::CalcTextSize(ICON_MD_SEARCH, NULL, true);
        const ImVec2 search_icon_pos(ImGui::GetItemRectMax().x - label_size.x - style.ItemInnerSpacing.x * 2, window->DC.CursorPos.y - ImGui::GetTextLineHeightWithSpacing());
        ImGui::RenderText(search_icon_pos, ICON_MD_SEARCH);
#endif

        ImGui::PopStyleColor(2);
        if (gi.pattern_buffer[0] != '\0')
            isNeedFilter = true;

        std::vector<SearchResult> SearchResults;
        if (isNeedFilter)
        {
            for (int i = 0; i < items_count; i++)
            {
                SearchResult result;
                if (FuzzySearch(gi.pattern_buffer, items[i].c_str(), result.Score, result.Matches, IM_ARRAYSIZE(result.Matches), result.MatchCount)) {
                    result.ItemIndex = i;
                    SearchResults.push_back(result);
                }
            }
            std::sort(SearchResults.begin(), SearchResults.end(), [](const SearchResult& a, const SearchResult& b) -> bool {
                // We want the biggest element first
                return a.Score > b.Score;
            });
        }

        int show_count = isNeedFilter ? SearchResults.size() : items_count;
        auto font_regular = ImGui::GetDrawListSharedData()->Font;
        auto font_highlight = ImGui::GetDrawListSharedData()->Font;

        ImU32 text_color_regular = ImGui::GetColorU32(ImGuiCol_Text);
        ImU32 text_color_highlight = ImGui::ColorConvertFloat4ToU32(ImVec4(24.0f/255.0f, 163.0f/255.0f, 1.0f, 1.0f));
        
        ImU32 item_hovered_color = ImGui::GetColorU32(ImGuiCol_HeaderHovered);
        ImU32 item_active_color = ImGui::GetColorU32(ImGuiCol_HeaderActive);
        ImU32 item_selected_color = ImGui::GetColorU32(ImGuiCol_Header);

        if (gi.ExtraData.size() < show_count)
            gi.ExtraData.resize(show_count);

        bool select_focused_item = false;
        if (ImGui::BeginListBox(label, size))
        {
            ImGuiWindow* window = ImGui::GetCurrentWindow();
            ImDrawList* draw_list = window->DrawList;
            const float font_size = window->CalcFontSize();

            for (int i = 0; i < show_count; ++i) {
                int idx = isNeedFilter ? SearchResults[i].ItemIndex : i;
                const bool item_selected = (idx == *current_item);
                const char* item_text = items[idx].c_str();
                ImGuiID id = window->GetID(static_cast<int>(i));

                ImGuiSelectableFlags flags = 0;
                
                const ImVec2 size_arg(0.0f, 0.0f);
                ImVec2 label_size = ImGui::CalcTextSize(item_text, NULL, true);
                ImVec2 size(size_arg.x != 0.0f ? size_arg.x : label_size.x, size_arg.y != 0.0f ? size_arg.y : label_size.y);
                ImVec2 pos = window->DC.CursorPos;
                pos.y += window->DC.CurrLineTextBaseOffset;

                // Fill horizontal space
                // We don't support (size < 0.0f) in Selectable() because the ItemSpacing extension would make explicitly right-aligned sizes not visibly match other widgets.
                const bool span_all_columns = (flags & ImGuiSelectableFlags_SpanAllColumns) != 0;
                const float min_x = span_all_columns ? window->ParentWorkRect.Min.x : pos.x;
                const float max_x = span_all_columns ? window->ParentWorkRect.Max.x : window->WorkRect.Max.x;
                if (size_arg.x == 0.0f || (flags & ImGuiSelectableFlags_SpanAvailWidth))
                    size.x = ImMax(label_size.x, max_x - min_x);

                // Text stays at the submission position, but bounding box may be extended on both sides
                // const ImVec2 text_min = pos;
                const ImVec2 text_max(min_x + size.x, pos.y + size.y);

                // Selectables are meant to be tightly packed together with no click-gap, so we extend their box to cover spacing between selectable.
                ImRect rect(min_x, pos.y, text_max.x, text_max.y);

                bool& hovered = gi.ExtraData[i].Hovered;
                bool& held = gi.ExtraData[i].Held;
                if (held && hovered) {
                    draw_list->AddRectFilled(rect.Min, rect.Max, item_active_color);
                } else if (hovered) {
                    draw_list->AddRectFilled(rect.Min, rect.Max, item_hovered_color);
                } else if (gi.CurrentSelectedItem == i) {
                    draw_list->AddRectFilled(rect.Min, rect.Max, item_selected_color);
                }

                if (isNeedFilter) {
                    // Iterating search results: draw text with highlights at matched chars

                    auto& search_result = SearchResults[i];

                    auto text_pos = window->DC.CursorPos;
                    int range_begin;
                    int range_end;
                    int last_range_end = 0;

                    auto DrawCurrentRange = [&]() {
                        if (range_begin != last_range_end) {
                            // Draw normal text between last highlighted range end and current highlighted range start
                            auto begin = item_text + last_range_end;
                            auto end = item_text + range_begin;
                            draw_list->AddText(text_pos, text_color_regular, begin, end);

                            auto segment_size = font_regular->CalcTextSizeA(font_size, std::numeric_limits<float>::max(), 0.0f, begin, end);
                            text_pos.x += segment_size.x;
                        }

                        auto begin = item_text + range_begin;
                        auto end = item_text + range_end;
                        draw_list->AddText(text_pos, text_color_highlight, begin, end);

                        auto segment_size = font_highlight->CalcTextSizeA(font_size, std::numeric_limits<float>::max(), 0.0f, begin, end);
                        text_pos.x += segment_size.x;
                    };

                    IM_ASSERT(search_result.MatchCount >= 1);
                    range_begin = search_result.Matches[0];
                    range_end = range_begin;

                    int last_char_idx = -1;
                    for (int j = 0; j < search_result.MatchCount; ++j) {
                        int char_idx = search_result.Matches[j];

                        if (char_idx == last_char_idx + 1) {
                            // These 2 indices are equal, extend our current range by 1
                            ++range_end;
                        } else {
                            DrawCurrentRange();
                            last_range_end = range_end;
                            range_begin = char_idx;
                            range_end = char_idx + 1;
                        }

                        last_char_idx = char_idx;
                    }

                    // Draw the remaining range (if any)
                    if (range_begin != range_end) {
                        DrawCurrentRange();
                    }

                    // Draw the text after the last range (if any)
                    draw_list->AddText(text_pos, text_color_regular, item_text + range_end); // Draw until \0
                } else {
                    // Iterating everything else: draw text as-is, there is no highlights
                    draw_list->AddText(pos, text_color_regular, item_text);
                }

                ImGui::ItemSize(rect);
                if (ImGui::ItemAdd(rect, id)) {                        
                    if (ImGui::ButtonBehavior(rect, id, &hovered, &held)) {
                        gi.CurrentSelectedItem = i;
                        select_focused_item = true;
                        value_changed = true;
                        *current_item = idx;
                        ImGui::CloseCurrentPopup();
                    }
                }
                
                if (item_selected)
                {
                    ImGui::SetItemDefaultFocus();
                    if (g.CurrentWindow->Appearing)
                    {
                        ImGui::SetScrollHereY(0.5f);
                    }
                }
            }


            ImGui::EndListBox();
        }
        ImGui::PopItemWidth();
    }

    if (value_changed)
        ImGui::MarkItemEdited(g.LastItemData.ID);

    return value_changed;
}


NS_CCIMGUI_END

@sweihub
Copy link

sweihub commented Sep 26, 2022

I have improved @ozlb version of ComboAutoSelect as follow

  1. Simplify the API
  2. Fixed some boundary issues of strcpy to strncpy
  3. Fixed the original fuzzy search function of not matching "List" keyword, replace with my own version
  4. Accept enter key to select the first match
  5. Support to using empty string as list item

GIF 2022-9-26 16-34-03

Demo

static ImGui::ComboAutoSelectData data = {{
				"",
				"AnimGraphNode_CopyBone",
				"ce skipaa",
				"ce skipscreen",
				"ce skipsplash",
				"ce skipsplashscreen",
				"client_unit.cpp",
				"letrograd",
				"level",
				"leveler",
				"MacroCallback.cpp",
				"Miskatonic university",
				"MockAI.h",
				"MockGameplayTasks.h",
				"MovieSceneColorTrack.cpp",
				"r.maxfps",
				"r.maxsteadyfps",
				"reboot",
				"rescale",
				"reset",
				"resource",
				"restart",
				"retrocomputer",
				"retrograd",
				"return",
				"slomo 10",
				"SVisualLoggerLogsList.h",
				"The Black Knight",
}};	
if (ImGui::ComboAutoSelect("my combofilter", data)) {
	// selection occurred
}
ImGui::Text("Selection: %s, index = %d", data.input, data.index);

Source files
https://github.com/sweihub/photon/blob/main/imgui/imgui_combo_autoselect.h
https://github.com/sweihub/photon/blob/main/imgui/imgui_combo_autoselect.cpp

@idbrii
Copy link
Contributor

idbrii commented Sep 28, 2022

@sweihub The magnifying glass isn't part of imgui or standard fonts. I use imgui from within bgfx and they setup several icon fonts as part of their build:

// bgfx packs kenney image font with its imgui and this is a magnifying glass.
static const char* ICON_FA_SEARCH = u8"\ue935";

These fonts use the unicode private use area, so they shouldn't conflict with your CJK fonts.

You can see how bgfx do it by following their use of s_iconsKenneyTtf. It's packed into a header (I assume to avoid including assets with their lib).

If you're already familiar with setting up imgui fonts, then it might be easier to add the font yourself. Here's the font in the bgfx repo.

See more information about the font in nicodinh/kenney-icon-font.


fts_fuzzy_match is maintained here could you report the issue and the fix there? I don't quite understand what went wrong for you (maybe two issues: not displaying CJK and crashing when filtering for CJK characters?).

@slajerek
Copy link

slajerek commented Oct 9, 2022

Thanks, this is a great topic, I'll definitely try to integrate these with my own code, you guys rock. Last time when I integrated this that simple UX case did not work: press TAB, press TAB, press Enter and select Dropdown, Enter text, press Enter.

@khlorz
Copy link

khlorz commented Feb 5, 2023

I tried to improved @sweihub's ComboAutoSelect by:

  • Making the combo filter items not limited to std::string and std::vectors
  • Use of std::span instead of void*
  • Encapsulation
  • Pros of CRTP

Of course, there are some cons to this:

  • Uses inheritance
  • Cons of using templated classes (increased compile time, increased binary size, etc.)
  • Cons of CRTP

Example:

struct Pair
{
	std::string Name;
	int         IDNumber;
};

class ComboFilterPair : public ComboFilter<Pair, ComboFilterPair>
{
public:
	ComboFilterPair(std::string_view combo_name, std::span<Pair> combo_items) :
		ComboFilter(combo_name, combo_items)
	{}

        // This is the getter function for the span of objects you need to represent as string
        // You can also make ComboFilter a friend of the inheriting class if you need GetItemString function to be private
	const char* GetItemString(int index) const
	{
		return Items[index].Name.c_str();
	}
};

static std::vector<Pair> vec_pair = { {"Pair1", 1}, {"PairTwo", 2}, {"PairNumber3", 3}, {"FourthPair", 4}, {"5thPair", 5} };
static ComboFilterPair combo_filter("Pair Combo Box", vec_pair);
if (combo_filter.Render()) {

}

https://gist.github.com/khlorz/5fbc89fa0c179341c6465fbca1425510

@khlorz
Copy link

khlorz commented Mar 19, 2023

Fixing my previous bad attempt at improving ComboAutoSelect #1658 (comment):

  • Uses templated functions instead of void* for type-safety
  • Improved visual components of the widget
  • Can work well with most standard containers and static c-style arrays
  • Can support user defined fuzzy search algorithm if needed
  • Fixed some minor bugs from previous iterations of ComboAutoSelect
#include <vector>

static const char* item_getter(const std::vector<std::string>& items, int index) {
   if (index >= 0 && index < (int)items.size()) {
       return items[index].c_str();
   }
   return "N/A";
}

static std::vector<std::string> items{ "instruction", "Chemistry", "Beating Around the Bush", "Instantaneous Combustion", "Level 999999", "nasal problems", "On cloud nine", "break the iceberg", "lacircificane" };
static char inputbuf[128];
static int selected_item = -1;
if (ImGui::ComboAutoSelect("std::vector combo", inputbuf, 128, selected_item, items, item_getter, ImGuiComboFlags_HeightSmall)) {
   /* Selection made */
}

combo_auto_select_demo
Required C++ standard: C++17 or later
https://github.com/khlorz/imgui-combo-filter

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests