From e8602a1ad504f571db3853e23d75e611514b9bfd Mon Sep 17 00:00:00 2001
From: Vsevolod Stakhov <vsevolod@highsecure.ru>
Date: Thu, 4 Jul 2019 15:49:27 +0100
Subject: [Minor] Add method to compare sorted tables

---
 lualib/lua_util.lua | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 46 insertions(+)

(limited to 'lualib')

diff --git a/lualib/lua_util.lua b/lualib/lua_util.lua
index fc4f33c83..7092aa3de 100644
--- a/lualib/lua_util.lua
+++ b/lualib/lua_util.lua
@@ -1044,4 +1044,50 @@ exports.values = function(gen, param, state)
   return values
 end
 
+---[[[
+-- @function lua_util.distance_sorted(t1, t2)
+-- Returns distance between two sorted tables t1 and t2
+-- @param {table} t1 input table
+-- @param {table} t2 input table
+-- @return distance between `t1` and `t2`
+--]]]
+exports.distance_sorted = function(t1, t2)
+  local ncomp = #t1
+  local ndiff = 0
+  local i,j = 1,1
+
+  if ncomp < #t2 then
+    ncomp = #t2
+  end
+
+  for _=1,ncomp do
+    if j > #t2 then
+      ndiff = ndiff + ncomp - #t2
+      if i > j then
+        ndiff = ndiff - (i - j)
+      end
+      break
+    elseif i > #t1 then
+      ndiff = ndiff + ncomp - #t1
+      if j > i then
+        ndiff = ndiff - (j - i)
+      end
+      break
+    end
+
+    if t1[i] == t2[j] then
+      i = i + 1
+      j = j + 1
+    elseif t1[i] < t2[j] then
+      i = i + 1
+      ndiff = ndiff + 1
+    else
+      j = j + 1
+      ndiff = ndiff + 1
+    end
+  end
+
+  return ndiff
+end
+
 return exports
-- 
cgit v1.2.3