[REQUEST] Prefix sorting

[BhasherBEL]

Before opening a feature request

• [X] I checked the next branch to see if the feature has already been implemented
• [X] I searched existing reports to see if it is already requested.

What is the user problem or growth opportunity you want to see solved?

When looking for an application, we usually search with it prefix. By example, when searching "O", "Onlyoffice" should be shown before "firefox". Thanks to https://github.com/davatorium/rofi/pull/1237, it's possible to match by prefix. But sometimes, we also search with another word. One good example is "DB Browser for SQLite". It would be nice to be able to sort by prefix, rather than match by it. That way, both uses cases works, and the arguments used in https://github.com/davatorium/rofi/pull/1237 are still true.

How do you know that this problem exists today? Why is this important?

I'm using rofi many times a day, and while it's awesome, there is sometimes too much friction, when there is a lot of applications.

Who will benefit from it?

Probably everybody, as it's a very common use case to start with the prefix.

Rofi version (rofi -v)

1.7.5+wayland3

Configuration

https://gist.github.com/BhasherBEL/674b236b9ae37a5734378b12b7fcdd62

Additional information

No response

[DaveDavenport]

What exactly do you mean with 'prefix' sorting? sort it alpha numeric on the full string? so it starts with a.... b..... etc.?

Something like:

diff --git a/include/settings.h b/include/settings.h
index 1af9b952..6a803441 100644
--- a/include/settings.h
+++ b/include/settings.h
@@ -46,7 +46,7 @@ typedef enum {
 /**
  * Possible sorting methods for listview.
  */
-typedef enum { SORT_NORMAL = 0, SORT_FZF = 1 } SortingMethod;
+typedef enum { SORT_NORMAL = 0, SORT_FZF = 1, SORT_ALNUM = 2 } SortingMethod;

 /**
  * Settings structure holding all (static) configurable options.
diff --git a/source/helper.c b/source/helper.c
index 53f366bf..0777cbde 100644
--- a/source/helper.c
+++ b/source/helper.c
@@ -653,6 +653,8 @@ int config_sanity_check(void) {
       config.sorting_method_enum = SORT_NORMAL;
     } else if (g_strcmp0(config.sorting_method, "fzf") == 0) {
       config.sorting_method_enum = SORT_FZF;
+    } else if (g_strcmp0(config.sorting_method, "alnum") == 0) {
+      config.sorting_method_enum = SORT_ALNUM;
     } else {
       g_string_append_printf(
           msg,
diff --git a/source/view.c b/source/view.c
index aac8c22e..a942f082 100644
--- a/source/view.c
+++ b/source/view.c
@@ -211,6 +211,28 @@ static int lev_sort(const void *p1, const void *p2, void *arg) {

   return distances[*a] - distances[*b];
 }
+static int alnum_sort(const void *p1, const void *p2, void *arg) {
+  const int *a = p1;
+  const int *b = p2;
+  RofiViewState *state = arg;
+
+  char *str_a = mode_get_completion(state->sw, *a);
+  char *str_b = mode_get_completion(state->sw, *b);
+
+  if (str_a == NULL && str_b == NULL) {
+    return 0;
+  } else if (str_a != NULL && str_b == NULL) {
+    g_free(str_a);
+    return -1;
+  } else if (str_a == NULL && str_b != NULL) {
+    g_free(str_b);
+    return -1;
+  }
+  int retv = g_utf8_collate(str_a, str_b);
+  g_free(str_a);
+  g_free(str_b);
+  return retv;
+}

 /**
  * Stores a screenshot of Rofi at that point in time.
@@ -765,6 +787,9 @@ static void filter_elements(thread_state *ts,
           t->state->distance[i] =
               rofi_scorer_fuzzy_evaluate(t->pattern, t->plen, str, slen);
           break;
+        case SORT_ALNUM:
+          t->state->distance[i] = 0;
+          break;
         case SORT_NORMAL:
         default:
           t->state->distance[i] = levenshtein(t->pattern, t->plen, str, slen);
@@ -1486,8 +1511,12 @@ static gboolean rofi_view_refilter_real(RofiViewState *state) {
       j += states[i].count;
     }
     if (config.sort) {
-      g_qsort_with_data(state->line_map, j, sizeof(int), lev_sort,
-                        state->distance);
+      if (config.sorting_method_enum == SORT_ALNUM) {
+        g_qsort_with_data(state->line_map, j, sizeof(int), alnum_sort, state);
+      } else {
+        g_qsort_with_data(state->line_map, j, sizeof(int), lev_sort,
+                          state->distance);
+      }
     }

     // Cleanup + bookkeeping.

-sorting-method alnum -sort

[BhasherBEL]

Not 100% sure about what g_utf8_collate do here.

The idea here is basically to prioritize entries where the match is at the beginning of the string. By example, when searching for "s", here is what happens now:

With this sorting method, Signal would be sorted first, because the match "s" is at the beginning.

[DaveDavenport]

What about using the fzf sorting method, as that put more weight on matching at the start?

rofi -sort -sorting-method fzf

[BhasherBEL]

It's a partial improvement, as it put more weight on smaller names. So from my experiments, it can both move them forward if they are small, but backward if the name is long.

[DaveDavenport]

Do you know of a weighting algorithm that does what you want?

[BhasherBEL]

I don't know if there is any algorithm that do that directly, but probably that a custom comparator could do it quite easily. I'm not used to C, but I could try to write an example if you want, maybe in a higher level language.

[DaveDavenport]

Yeah, a high level algo would be useful.. In my experience it sounds easier then it is, for us (knowing what we are looking for ) it sounds obvious, but it often isn't to implement.

With the current information, I don't know what would fit your requirements.

Currently rofi works with 'distances', the lower the distance the higher it is in the list.

[BhasherBEL]

No problem, converting words and ideas into code is indeed not an easy task.

If I stick to a high level language such as python, I would write this kind of comparator function, with a and b the variables to compare, input what the users typed, and distance the current distance-based algorithm.

As we can see, it's not so much a new algorithm, but rather a "shortcut" for the case where an entry starts with the input.

def compare(a: str, b: str, input: str):
    if a.startswith(input) and not b.startswith(input):
        return 1
    elif b.startswith(input) and not a.startswith(input):
        return -1
    else:
        return distance(a, b, index)

[DaveDavenport]

This would most likely favour shorter words just like the fzf algorithm.

[DaveDavenport]

diff --git a/include/settings.h b/include/settings.h
index 1af9b952..6a803441 100644
--- a/include/settings.h
+++ b/include/settings.h
@@ -46,7 +46,7 @@ typedef enum {
 /**
  * Possible sorting methods for listview.
  */
-typedef enum { SORT_NORMAL = 0, SORT_FZF = 1 } SortingMethod;
+typedef enum { SORT_NORMAL = 0, SORT_FZF = 1, SORT_ALNUM = 2 } SortingMethod;

 /**
  * Settings structure holding all (static) configurable options.
diff --git a/source/helper.c b/source/helper.c
index 53f366bf..0777cbde 100644
--- a/source/helper.c
+++ b/source/helper.c
@@ -653,6 +653,8 @@ int config_sanity_check(void) {
       config.sorting_method_enum = SORT_NORMAL;
     } else if (g_strcmp0(config.sorting_method, "fzf") == 0) {
       config.sorting_method_enum = SORT_FZF;
+    } else if (g_strcmp0(config.sorting_method, "alnum") == 0) {
+      config.sorting_method_enum = SORT_ALNUM;
     } else {
       g_string_append_printf(
           msg,
diff --git a/source/view.c b/source/view.c
index aac8c22e..c611e3fe 100644
--- a/source/view.c
+++ b/source/view.c
@@ -211,6 +211,38 @@ static int lev_sort(const void *p1, const void *p2, void *arg) {

   return distances[*a] - distances[*b];
 }
+static int alnum_sort(const void *p1, const void *p2, void *arg) {
+  const int *a = p1;
+  const int *b = p2;
+  RofiViewState *state = arg;
+  int *distances = state->distance;
+
+  char *str_a = mode_get_completion(state->sw, *a);
+  char *str_b = mode_get_completion(state->sw, *b);
+
+  if (str_a == NULL && str_b == NULL) {
+    return 0;
+  } else if (str_a != NULL && str_b == NULL) {
+    g_free(str_a);
+    return -1;
+  } else if (str_a == NULL && str_b != NULL) {
+    g_free(str_b);
+    return -1;
+  }
+
+  char *str = state->text->text;
+  size_t l = strlen(str);
+  if (strncasecmp(str_a, str, l) == 0 && strncasecmp(str_b, str, l) != 0) {
+    return -1;
+  } else if (strncasecmp(str_b, str, l) == 0 &&
+             strncasecmp(str_a, str, l) != 0) {
+    return 1;
+  }
+  int retv = distances[*a] - distances[*b];
+  g_free(str_a);
+  g_free(str_b);
+  return retv;
+}

 /**
  * Stores a screenshot of Rofi at that point in time.
@@ -765,9 +797,13 @@ static void filter_elements(thread_state *ts,
           t->state->distance[i] =
               rofi_scorer_fuzzy_evaluate(t->pattern, t->plen, str, slen);
           break;
+        case SORT_ALNUM:
+          t->state->distance[i] = levenshtein(t->pattern, t->plen, str, slen);
+          break;
         case SORT_NORMAL:
         default:
           t->state->distance[i] = levenshtein(t->pattern, t->plen, str, slen);
+          printf("%d %s\n", t->state->distance[i], str);
           break;
         }
         g_free(str);
@@ -1486,8 +1522,12 @@ static gboolean rofi_view_refilter_real(RofiViewState *state) {
       j += states[i].count;
     }
     if (config.sort) {
-      g_qsort_with_data(state->line_map, j, sizeof(int), lev_sort,
-                        state->distance);
+      if (config.sorting_method_enum == SORT_ALNUM) {
+        g_qsort_with_data(state->line_map, j, sizeof(int), alnum_sort, state);
+      } else {
+        g_qsort_with_data(state->line_map, j, sizeof(int), lev_sort,
+                          state->distance);
+      }
     }

     // Cleanup + bookkeeping.

[BhasherBEL]

I tried your patch, but wasn't able to see any difference when using rofi -modes run -show run -sorting-method alnum compared to the default option. Do you see any difference on your side?

In this example, I would except Thunderbird to be ranked way higher than it actually is, as it starts with the user input.

[DaveDavenport]

Pass -sort to enable sorting?

[DaveDavenport]

[BhasherBEL]

Ok, feel a bit stupid now :sweat_smile: Thank you a lot, that was exactly what I was looking for!

Any plan to merge this into rofi itself?

[DaveDavenport]

I need to see how to do this utf-8 safe, but I don't see a reason to not merge it.