From 444bcd43b724af6609b44cf864d2d1b8267a0a30 Mon Sep 17 00:00:00 2001
From: dyphire <qimoge@gmail.com>
Date: Tue, 25 Oct 2022 05:02:00 +0800
Subject: TOOLS/lua/autoload: further optimize the natural sorting

Commits https://github.com/mpv-player/mpv/commit/257dbdf06feb366f9eb1f96ceb7026c9365dddaa uses a algorithm of splitting strings
into a table of number and string values to achieve natural sorting.
This approach works well in most cases, but it does not work well
in some specific scenarios.
Now let's implement natural sorting with a stronger algorithm.

Also fixes indentation.

Ref: https://github.com/jonniek/mpv-playlistmanager/commit/3cf323f3c419af77f4141119283c1ec2911491c5
Closes https://github.com/mpv-player/mpv/issues/8969
---
 TOOLS/lua/autoload.lua | 54 ++++++++++++++++++--------------------------------
 1 file changed, 19 insertions(+), 35 deletions(-)

(limited to 'TOOLS')

diff --git a/TOOLS/lua/autoload.lua b/TOOLS/lua/autoload.lua
index 048ecdedb0..f43272eee6 100644
--- a/TOOLS/lua/autoload.lua
+++ b/TOOLS/lua/autoload.lua
@@ -94,47 +94,31 @@ table.filter = function(t, iter)
     end
 end
 
--- splitbynum and alnumcomp from alphanum.lua (C) Andre Bogus
--- Released under the MIT License
--- http://www.davekoelle.com/files/alphanum.lua
-
--- split a string into a table of number and string values
-function splitbynum(s)
-    local result = {}
-    for x, y in (s or ""):gmatch("(%d*)(%D*)") do
-        if x ~= "" then table.insert(result, tonumber(x)) end
-        if y ~= "" then table.insert(result, y) end
-    end
-    return result
-end
-
-function clean_key(k)
-    k = (' '..k..' '):gsub("%s+", " "):sub(2, -2):lower()
-    return splitbynum(k)
-end
+-- alphanum sorting for humans in Lua
+-- http://notebook.kulchenko.com/algorithms/alphanumeric-natural-sorting-for-humans-in-lua
 
--- compare two strings
-function alnumcomp(x, y)
-    local xt, yt = clean_key(x), clean_key(y)
-    for i = 1, math.min(#xt, #yt) do
-        local xe, ye = xt[i], yt[i]
-        if type(xe) == "string" then ye = tostring(ye)
-        elseif type(ye) == "string" then xe = tostring(xe) end
-        if xe ~= ye then return xe < ye end
+function alphanumsort(o)
+    local function padnum(d)
+        local dec, n = string.match(d, "(%.?)0*(.+)")
+        return #dec > 0 and ("%.12f"):format(d) or ("%s%03d%s"):format(dec, #n, n)
     end
-    return #xt < #yt
+    table.sort(o, function(a,b)
+        return tostring(a):lower():gsub("%.?%d+",padnum)..("%3d"):format(#b)
+             < tostring(b):lower():gsub("%.?%d+",padnum)..("%3d"):format(#a) 
+    end)
+    return o
 end
 
 local autoloaded = nil
 
 function get_playlist_filenames()
-  local filenames = {}
-  for n = 0, pl_count - 1, 1 do
-    local filename = mp.get_property('playlist/'..n..'/filename')
-    local _, file = utils.split_path(filename)
-    filenames[file] = true
-  end
-  return filenames
+    local filenames = {}
+    for n = 0, pl_count - 1, 1 do
+        local filename = mp.get_property('playlist/'..n..'/filename')
+        local _, file = utils.split_path(filename)
+        filenames[file] = true
+    end
+    return filenames
 end
 
 function find_and_add_entries()
@@ -181,7 +165,7 @@ function find_and_add_entries()
         end
         return EXTENSIONS[string.lower(ext)]
     end)
-    table.sort(files, alnumcomp)
+    alphanumsort(files)
 
     if dir == "." then
         dir = ""
-- 
cgit v1.2.3