CharacterMap: Add a find-by-name window

This works the same way as the command-line usage, searching against the
display name as provided by LibUnicode.

I've modified the search loop to cover every possible unicode
code-point, since my previous logic was flawed. Code-points are not
dense, there are gaps, so simply iterating up to the count of them will
skip ones with higher values. Surprisingly, iterating all 1,114,112 of
them still runs in a third of a second. Computers are fast!

8 files changed, 202 insertions, 24 deletions

diff --git a/Userland/Applications/CharacterMap/CMakeLists.txt b/Userland/Applications/CharacterMap/CMakeLists.txt
index d675fba38e..c78e04ddc2 100644
--- a/Userland/Applications/CharacterMap/CMakeLists.txt
+++ b/Userland/Applications/CharacterMap/CMakeLists.txt
@@ -5,10 +5,13 @@ serenity_component(
 )
 
 compile_gml(CharacterMapWindow.gml CharacterMapWindowGML.h character_map_window_gml)
+compile_gml(CharacterSearchWindow.gml CharacterSearchWindowGML.h character_search_window_gml)
 
 set(SOURCES
-    CharacterMapWindowGML.h
     CharacterMapWidget.cpp
+    CharacterMapWindowGML.h
+    CharacterSearchWidget.cpp
+    CharacterSearchWindowGML.h
     main.cpp
 )
 
diff --git a/Userland/Applications/CharacterMap/CharacterMapWidget.cpp b/Userland/Applications/CharacterMap/CharacterMapWidget.cpp
index 553b1326e1..82e4b90108 100644
--- a/Userland/Applications/CharacterMap/CharacterMapWidget.cpp
+++ b/Userland/Applications/CharacterMap/CharacterMapWidget.cpp
@@ -5,6 +5,7 @@
  */
 
 #include "CharacterMapWidget.h"
+#include "CharacterSearchWidget.h"
 #include <AK/StringUtils.h>
 #include <Applications/CharacterMap/CharacterMapWindowGML.h>
 #include <LibConfig/Client.h>
@@ -76,6 +77,23 @@ CharacterMapWidget::CharacterMapWidget()
     });
     m_go_to_glyph_action->set_status_tip("Go to the specified code point");
 
+    m_find_glyphs_action = GUI::Action::create("&Find glyphs...", { Mod_Ctrl, Key_F }, Gfx::Bitmap::try_load_from_file("/res/icons/16x16/find.png").release_value_but_fixme_should_propagate_errors(), [&](auto&) {
+        if (m_find_window.is_null()) {
+            m_find_window = GUI::Window::construct(window());
+            auto& search_widget = m_find_window->set_main_widget<CharacterSearchWidget>();
+            search_widget.on_character_selected = [&](auto code_point) {
+                m_glyph_map->set_active_glyph(code_point);
+                m_glyph_map->scroll_to_glyph(code_point);
+            };
+            m_find_window->set_icon(GUI::Icon::try_create_default_icon("find").value().bitmap_for_size(16));
+            m_find_window->set_title("Find a character");
+            m_find_window->resize(300, 400);
+        }
+        m_find_window->show();
+        m_find_window->move_to_front();
+        m_find_window->find_descendant_of_type_named<GUI::TextBox>("search_input")->set_focus(true);
+    });
+
     m_toolbar->add_action(*m_choose_font_action);
     m_toolbar->add_separator();
     m_toolbar->add_action(*m_copy_selection_action);
@@ -83,6 +101,7 @@ CharacterMapWidget::CharacterMapWidget()
     m_toolbar->add_action(*m_previous_glyph_action);
     m_toolbar->add_action(*m_next_glyph_action);
     m_toolbar->add_action(*m_go_to_glyph_action);
+    m_toolbar->add_action(*m_find_glyphs_action);
 
     m_glyph_map->on_active_glyph_changed = [&](int) {
         update_statusbar();
diff --git a/Userland/Applications/CharacterMap/CharacterMapWidget.h b/Userland/Applications/CharacterMap/CharacterMapWidget.h
index 0b57a35a01..fdf304eaf9 100644
--- a/Userland/Applications/CharacterMap/CharacterMapWidget.h
+++ b/Userland/Applications/CharacterMap/CharacterMapWidget.h
@@ -30,10 +30,12 @@ private:
     RefPtr<GUI::TextBox> m_output_box;
     RefPtr<GUI::Button> m_copy_output_button;
     RefPtr<GUI::Statusbar> m_statusbar;
+    RefPtr<GUI::Window> m_find_window;
 
     RefPtr<GUI::Action> m_choose_font_action;
     RefPtr<GUI::Action> m_copy_selection_action;
     RefPtr<GUI::Action> m_previous_glyph_action;
     RefPtr<GUI::Action> m_next_glyph_action;
     RefPtr<GUI::Action> m_go_to_glyph_action;
+    RefPtr<GUI::Action> m_find_glyphs_action;
 };
diff --git a/Userland/Applications/CharacterMap/CharacterSearchWidget.cpp b/Userland/Applications/CharacterMap/CharacterSearchWidget.cpp
new file mode 100644
index 0000000000..f52335e107
--- /dev/null
+++ b/Userland/Applications/CharacterMap/CharacterSearchWidget.cpp
@@ -0,0 +1,91 @@
+/*
+ * Copyright (c) 2022, Sam Atkins <atkinssj@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include "CharacterSearchWidget.h"
+#include "SearchCharacters.h"
+#include <Applications/CharacterMap/CharacterSearchWindowGML.h>
+
+struct SearchResult {
+    u32 code_point;
+    String display_text;
+};
+
+class CharacterSearchModel final : public GUI::Model {
+public:
+    CharacterSearchModel() { }
+
+    int row_count(GUI::ModelIndex const&) const override { return m_data.size(); }
+    int column_count(GUI::ModelIndex const&) const override { return 1; }
+
+    GUI::Variant data(GUI::ModelIndex const& index, GUI::ModelRole role) const override
+    {
+        auto& result = m_data.at(index.row());
+        if (role == GUI::ModelRole::Display)
+            return result.display_text;
+        if (role == GUI::ModelRole::Custom)
+            return result.code_point;
+        return {};
+    }
+
+    void clear()
+    {
+        m_data.clear();
+        invalidate();
+    }
+
+    void add_result(SearchResult result)
+    {
+        m_data.append(move(result));
+        invalidate();
+    }
+
+private:
+    Vector<SearchResult> m_data;
+};
+
+CharacterSearchWidget::CharacterSearchWidget()
+{
+    load_from_gml(character_search_window_gml);
+
+    m_search_input = find_descendant_of_type_named<GUI::TextBox>("search_input");
+    m_search_button = find_descendant_of_type_named<GUI::Button>("search_button");
+    m_results_list = find_descendant_of_type_named<GUI::ListView>("results_list");
+
+    m_search_input->on_return_pressed = [this] { search(); };
+    m_search_button->on_click = [this](auto) { search(); };
+
+    m_results_list->horizontal_scrollbar().set_visible(false);
+    m_results_list->set_model(adopt_ref(*new CharacterSearchModel()));
+    m_results_list->on_activation = [&](GUI::ModelIndex const& index) {
+        auto& model = static_cast<CharacterSearchModel&>(*m_results_list->model());
+        auto code_point = model.data(index, GUI::ModelRole::Custom).as_u32();
+        if (on_character_selected)
+            on_character_selected(code_point);
+    };
+}
+
+CharacterSearchWidget::~CharacterSearchWidget()
+{
+}
+
+void CharacterSearchWidget::search()
+{
+    // TODO: Sort the results nicely. They're sorted by code-point for now, which is easy, but not the most useful.
+    //       Sorting intelligently in a style similar to Assistant would be nicer.
+    auto& model = static_cast<CharacterSearchModel&>(*m_results_list->model());
+    model.clear();
+    auto query = m_search_input->text();
+    if (query.is_empty())
+        return;
+    for_each_character_containing(query, [&](auto code_point, auto& display_name) {
+        StringBuilder builder;
+        builder.append_code_point(code_point);
+        builder.append(" - ");
+        builder.append(display_name);
+
+        model.add_result({ code_point, builder.to_string() });
+    });
+}
diff --git a/Userland/Applications/CharacterMap/CharacterSearchWidget.h b/Userland/Applications/CharacterMap/CharacterSearchWidget.h
new file mode 100644
index 0000000000..8109246663
--- /dev/null
+++ b/Userland/Applications/CharacterMap/CharacterSearchWidget.h
@@ -0,0 +1,30 @@
+/*
+ * Copyright (c) 2022, Sam Atkins <atkinssj@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include "CharacterMapWidget.h"
+#include <LibGUI/Button.h>
+#include <LibGUI/ListView.h>
+#include <LibGUI/TextBox.h>
+
+class CharacterSearchWidget final : public GUI::Widget {
+    C_OBJECT(CharacterSearchWidget);
+
+public:
+    virtual ~CharacterSearchWidget() override;
+
+    Function<void(u32)> on_character_selected;
+
+private:
+    CharacterSearchWidget();
+
+    void search();
+
+    RefPtr<GUI::TextBox> m_search_input;
+    RefPtr<GUI::Button> m_search_button;
+    RefPtr<GUI::ListView> m_results_list;
+};
diff --git a/Userland/Applications/CharacterMap/CharacterSearchWindow.gml b/Userland/Applications/CharacterMap/CharacterSearchWindow.gml
new file mode 100644
index 0000000000..aa7079a097
--- /dev/null
+++ b/Userland/Applications/CharacterMap/CharacterSearchWindow.gml
@@ -0,0 +1,21 @@
+@GUI::Frame {
+    layout: @GUI::VerticalBoxLayout {
+    }
+
+    fill_with_background_color: true
+
+    @GUI::Toolbar {
+        @GUI::TextBox {
+            name: "search_input"
+        }
+        @GUI::Button {
+            name: "search_button"
+            icon: "/res/icons/16x16/find.png"
+            fixed_width: 22
+        }
+    }
+
+    @GUI::ListView {
+        name: "results_list"
+    }
+}
diff --git a/Userland/Applications/CharacterMap/SearchCharacters.h b/Userland/Applications/CharacterMap/SearchCharacters.h
new file mode 100644
index 0000000000..ef5e76ee5c
--- /dev/null
+++ b/Userland/Applications/CharacterMap/SearchCharacters.h
@@ -0,0 +1,26 @@
+/*
+ * Copyright (c) 2022, Sam Atkins <atkinssj@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <AK/String.h>
+#include <LibUnicode/CharacterTypes.h>
+
+template<typename Callback>
+void for_each_character_containing(StringView query, Callback callback)
+{
+    String uppercase_query = query.to_uppercase_string();
+    StringView uppercase_query_view = uppercase_query.view();
+    constexpr u32 maximum_code_point = 0x10FFFF;
+    // FIXME: There's probably a better way to do this than just looping, but it still only takes ~150ms to run for me!
+    for (u32 code_point = 1; code_point <= maximum_code_point; ++code_point) {
+        if (auto maybe_display_name = Unicode::code_point_display_name(code_point); maybe_display_name.has_value()) {
+            auto& display_name = maybe_display_name.value();
+            if (display_name.contains(uppercase_query_view, AK::CaseSensitivity::CaseSensitive))
+                callback(code_point, display_name);
+        }
+    }
+}
diff --git a/Userland/Applications/CharacterMap/main.cpp b/Userland/Applications/CharacterMap/main.cpp
index 2764a797a5..0447481f20 100644
--- a/Userland/Applications/CharacterMap/main.cpp
+++ b/Userland/Applications/CharacterMap/main.cpp
@@ -5,6 +5,7 @@
  */
 
 #include "CharacterMapWidget.h"
+#include "SearchCharacters.h"
 #include <LibConfig/Client.h>
 #include <LibCore/ArgsParser.h>
 #include <LibCore/System.h>
@@ -13,34 +14,19 @@
 #include <LibGUI/Window.h>
 #include <LibGfx/FontDatabase.h>
 #include <LibMain/Main.h>
-#include <LibUnicode/CharacterTypes.h>
 
 static void search_and_print_results(String const& query)
 {
     outln("Searching for '{}'", query);
-    String uppercase_query = query.to_uppercase();
-    StringView uppercase_query_view = uppercase_query.view();
-    // FIXME: At time of writing there are 144,697 code points in Unicode. I've added some breathing room,
-    //        but ideally this would be defined in LibUnicode somewhere.
-    constexpr u32 unicode_character_count = 150000;
-    // FIXME: There's probably a better way to do this than just looping, but it still only takes ~150ms to run for me!
     u32 result_count = 0;
-    for (u32 i = 1; i < unicode_character_count; ++i) {
-        if (auto maybe_display_name = Unicode::code_point_display_name(i); maybe_display_name.has_value()) {
-            auto& display_name = maybe_display_name.value();
-            // FIXME: This should be a case-sensitive search, since we already converted the query to uppercase
-            //        and the unicode names are all in uppercase. But, that makes it run slower!
-            //        Sensitive: ~175ms, Insensitive: ~140ms
-            if (display_name.contains(uppercase_query_view, AK::CaseSensitivity::CaseInsensitive)) {
-                StringBuilder builder;
-                builder.append_code_point(i);
-                builder.append(" - ");
-                builder.append(display_name);
-                outln(builder.string_view());
-                result_count++;
-            }
-        }
-    }
+    for_each_character_containing(query, [&](auto code_point, auto& display_name) {
+        StringBuilder builder;
+        builder.append_code_point(code_point);
+        builder.append(" - ");
+        builder.append(display_name);
+        outln(builder.string_view());
+        result_count++;
+    });
 
     if (result_count == 0)
         outln("No results found.");